Submission #153115

#	Time	Username	Problem	Language	Result	Execution time	Memory
153115		popovicirobert	Last supper (IOI12_supper)	C++14	0 / 100	66 ms	7664 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 {
            pos[prev(pq.end()) -> second] = -1;
            pq.erase(prev(pq.end()));
        }
        pq.insert({nxt[i], i + k});
        /*for(auto it : pq) {
            cerr << it.first << " " << it.second << "\n";
        }
        cerr << "\n";*/
        pos[C[i]] = i + k;
    }

    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] - '0' << " ";
    }*/

    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) {
            PutBack(*bad.begin());
            col.erase(*bad.begin());
            bad.erase(bad.begin());
        }
        if(A[i] == '0') {
            bad.insert(cur);
        }
        col.insert(cur);
    }

}

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