cpinitiative / usaco-guide

A free collection of curated, high-quality resources to take you from Bronze to Platinum and beyond.
https://usaco.guide
Other
1.62k stars 493 forks source link

WA on Groups but AC on CSES #2589

Open Evang264 opened 2 years ago

Evang264 commented 2 years ago
#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.

MckinleyX commented 2 years ago

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.

thecodingwizard commented 2 years ago

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?