usaco-guide
usaco-guide copied to clipboard
WA on Groups but AC on CSES
#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.
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.
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?