Submission #374960

# Submission time Handle Problem Language Result Execution time Memory
374960 2021-03-08T17:03:53 Z gustason Fire drill (LMIO18_sauga) C++14
21.1844 / 100
54 ms 7788 KB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
    int cnt, in, idx;
    bool operator<(Node other) {
        if (in + cnt == other.in + cnt)
            return idx < other.idx;
        return in + cnt < other.in + cnt;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(0));
    int t, n, S;
    cin >> t >> n >> S;

    vector<int> cant[n+1], in[n+1];
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        for(int j = 0; j < m; j++) {
            int x;
            cin >> x;
            cant[i].push_back(x);
            in[x].push_back(i);
        }
    }

    set<pair<int, int>> s;
    vector<int> cnt(n+1), inn(n+1);
    for(int i = 0; i < n; i++) {
        s.insert({cant[i].size(), i});
        cnt[i] = cant[i].size();
        inn[i] = in[i].size();
    }

    vector<bool> done(n+1, false);
    vector<int> ans;

    for(int i = 0; i < n; i++) {
        int best = -n, idx = 0;
        for(int j = 0; j < n; j++) {
            if (done[j]) continue;
            if (inn[i] - cnt[i] > best) {
                best = inn[i] - cnt[i];
                idx = j;
            }
        }

        done[idx] = true;
        ans.push_back(idx);

        for(int j : in[idx]) {
            cnt[j]--;
        }
        for(int j : cant[idx]) {
            inn[j]--;
        }
//        auto it = s.begin();
//        while(1) {
//            it = s.begin();
//            if (done[(*it).second]) {
//                s.erase(it);
//                continue;
//            }
//            break;
//        }
//        done[(*it).second] = true;
//        ans.push_back((*it).second);
//        s.erase(it);
//        for(int j : in[(*it).second]) {
//            s.erase({cnt[j], j});
//            cnt[j]--;
//            s.insert({cnt[j], j});
//        }
    }

    for(int i : ans) {
        cout << i + 1 << "\n";
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 7660 KB Output isn't correct
2 Partially correct 3 ms 492 KB Output is partially correct
3 Partially correct 3 ms 492 KB Output is partially correct
4 Partially correct 3 ms 620 KB Output is partially correct
5 Partially correct 2 ms 492 KB Output is partially correct
6 Partially correct 3 ms 620 KB Output is partially correct
7 Partially correct 11 ms 1644 KB Output is partially correct
8 Incorrect 54 ms 7788 KB Output isn't correct
9 Partially correct 8 ms 1132 KB Output is partially correct
10 Partially correct 2 ms 492 KB Output is partially correct