Submission #374962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
374962	2021-03-08T17:04:24 Z	gustason	Fire drill (LMIO18_sauga)	C++14	31.1577 / 100	58 ms	5868 KB

sauga

#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 (cnt[i] - inn[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;
}

Subtask #1

31.1577033891 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	58 ms	5740 KB	Output is partially correct
2	Partially correct	2 ms	492 KB	Output is partially correct
3	Partially correct	3 ms	492 KB	Output is partially correct
4	Partially correct	3 ms	492 KB	Output is partially correct
5	Partially correct	3 ms	492 KB	Output is partially correct
6	Partially correct	3 ms	492 KB	Output is partially correct
7	Partially correct	11 ms	1388 KB	Output is partially correct
8	Partially correct	55 ms	5868 KB	Output is partially correct
9	Partially correct	8 ms	1004 KB	Output is partially correct
10	Partially correct	2 ms	492 KB	Output is partially correct