Submission #362235

#	Time	Username	Problem	Language	Result	Execution time	Memory
362235		benedict0724	Last supper (IOI12_supper)	C++17	100 / 100	168 ms	74072 KiB

advisor

#include "advisor.h"
#include <queue>
using namespace std;
const int INF = 1000000000;

queue<int> useWhen[100000];
queue<int> ret;
priority_queue<pair<int, int>> pq;
pair<int, int> shelf[100000]; int loc[100000];
bool use[100000], initial[100000], removable[100000];
void ComputeAdvice(int *C, int N, int K, int M) {

    for(int i=0;i<N;i++) useWhen[C[i]].push(i);
    for(int i=0;i<K;i++) {
        shelf[i] = {i, -1}; use[i] = true; loc[i] = i;
        if(useWhen[i].empty()) pq.push({INF, i});
        else pq.push({useWhen[i].front(), i});
    }

    for(int i=0;i<N;i++){
        if(!use[C[i]]){
            int m = pq.top().second; pq.pop();

            use[shelf[m].first] = false;
            use[C[i]] = true;
            loc[C[i]] = m;

            shelf[m] = {C[i], i};
            useWhen[C[i]].pop();

            if(useWhen[C[i]].empty()) pq.push({INF, m});
            else pq.push({useWhen[C[i]].front(), m});
        }
        else{
            useWhen[C[i]].pop();
            if(useWhen[C[i]].empty()) pq.push({INF, loc[C[i]]});
            else pq.push({useWhen[C[i]].front(), loc[C[i]]});

            if(shelf[loc[C[i]]].second != -1)
                removable[shelf[loc[C[i]]].second] = true;
            else
                initial[C[i]] = true;

            shelf[loc[C[i]]].second = i;
        }
    }

    for(int i=0;i<K;i++){
        WriteAdvice(initial[i]);
    }
    for(int i=0;i<N;i++){
        WriteAdvice(removable[i]);
    }
}

assistant

#include "assistant.h"
#include <queue>
std::queue<int> toRemove; bool Using[100000];

void Assist(unsigned char *A, int N, int K, int R) {
    for(int i=0;i<K;i++){
        if(!A[i]) toRemove.push(i);
        Using[i] = true;
    }
    for(int i=0;i<N;i++){
        int req = GetRequest();
        if(Using[req]){
            if(!A[K + i]) toRemove.push(req);
            continue;
        }

        int rem = toRemove.front(); toRemove.pop();

        Using[rem] = false;
        Using[req] = true;

        if(!A[K + i]) toRemove.push(req);
        PutBack(rem);
    }
}

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