Submission #153120

#	Time	Username	Problem	Language	Result	Execution time	Memory
153120		popovicirobert	최후의 만찬 (IOI12_supper)	C++14	100 / 100	212 ms	10196 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;


void ComputeAdvice(int *C, int n, int k, int M) {

    vector <int> last(n, n), nxt(n);
    int i;

    for(i = n - 1; i >= 0; i--) {
        nxt[i] = last[C[i]];
        last[C[i]] = i;
    }

    set < pair <int, int> > pq;
    vector <int> pos(n, -1);

    for(i = 0; i < k; i++) {
        pq.insert({last[i], i});
        pos[i] = i;
    }

    vector <unsigned char> sol(n + k, 0);
    for(i = 0; i < n; i++) {
        if(pos[C[i]] != -1) {
            sol[pos[C[i]]] = 1;
            pq.erase(pq.lower_bound({i, -1}));
        }
        else {
            int p = prev(pq.end()) -> second;
            if(p < k) {
                pos[p] = -1;
            }
            else {
                pos[C[p - k]] = -1;
            }
            pq.erase(prev(pq.end()));
        }
        pq.insert({nxt[i], i + k});
        pos[C[i]] = i + k;
        /*for(auto it : pq) {
            cerr << it.first << " " << it.second << "\n";
        }
        cerr << "\n";*/
    }

    for(auto it : sol) {
        WriteAdvice(it);
    }
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

void Assist(unsigned char *A, int n, int k, int R) {
    set <int> col, bad;
    int i;

    /*cerr << n + k << "\n";
    for(i = 0; i < n + k; i++) {
        cerr << (int) A[i] << " ";
    }*/

    for(i = 0; i < k; i++) {
        col.insert(i);
        if(A[i] == 0) {
            bad.insert(i);
        }
    }

    for(i = k; i < n + k; i++) {
        int cur = GetRequest();
        if(col.count(cur) == 0) {
            if(bad.size() == 0) {
                while(1) {

                }
            }
            PutBack(*bad.begin());
            col.erase(*bad.begin());
            bad.erase(bad.begin());
        }
        if(A[i] == 0) {
            bad.insert(cur);
        }
        col.insert(cur);
    }

}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39