usaco-guide icon indicating copy to clipboard operation
usaco-guide copied to clipboard

WA on Groups but AC on CSES

Open Evang264 opened this issue 3 years ago • 2 comments

#include <bits/stdc++.h>
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
const int N = 2e5+5;
int n, ans[N];
struct per {
	int l, r, id;
} a[N];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("debug.txt", "w", stderr);
#endif
 
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
	}
 
	sort(a, a+n, [](per x, per y){
		return x.l < y.l;
	});
 
	// holds rooms represented by pairs of the form (departure time, room ID)
	minpq<pair<int, int>> rooms;
	rooms.emplace(0, 1);
	for(int i = 0; i < n; ++i){
		if(rooms.top().first < a[i].l){
			ans[a[i].id] = rooms.top().second;
			rooms.pop();
		}else
			ans[a[i].id] = rooms.size() + 1;
 
		rooms.emplace(a[i].r, ans[a[i].id]);
	}
 
	cout << rooms.size() << '\n';
	for(int i = 0; i < n; ++i)
		cout << ans[i] << " \n"[i==n-1];
}

The above code works on https://cses.fi/problemset/task/1164 but not on Groups (it gets 16.7/100 points). This problem is viewable in the Week 4 homework of this semester's silver class.

Evang264 avatar Feb 20 '22 04:02 Evang264

Most likely the issue happens because the problem has multiple correct answers, and CSES accepts any of them, whereas the guide grader only accepts one.

MckinleyX avatar Feb 20 '22 05:02 MckinleyX

It's theoretically possible to implement a grader (~4 hours?). But unless this is an issue that affects many problems, it might be better to just tell students to submit their code to CSES website for now?

thecodingwizard avatar Jun 22 '22 08:06 thecodingwizard