Submission #361969

#	Time	Username	Problem	Language	Result	Execution time	Memory
361969		benedict0724	Last supper (IOI12_supper)	C++17	43 / 100	368 ms	79712 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;
int shelf[100000], loc[100000];
bool use[100000];
void ComputeAdvice(int *C, int N, int K, int M) {
    int logK = 0;
    while((1<<logK) <= K) logK++;

    for(int i=0;i<N;i++) useWhen[C[i]].push(i);
    for(int i=0;i<K;i++) {
        shelf[i] = i; 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]] = false;
            use[C[i]] = true;

            ret.push(m);
            shelf[m] = C[i];
            useWhen[C[i]].pop();
            loc[C[i]] = m;
            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]]});
        }
    }

    while(!ret.empty()){
        int now = ret.front(); ret.pop();
        for(int i=logK-1;i>=0;i--){
            if((1<<i) & now) WriteAdvice(1);
            else WriteAdvice(0);
        }
    }
}

assistant

#include "assistant.h"
bool usea[100000]; int sh[100000];

void Assist(unsigned char *A, int N, int K, int R) {
    int i, logK = 0, cnt = 0;
    while((1<<logK) <= K) logK++;
    for (i = 0; i < K; i++) {
        usea[i] = true;
        sh[i] = i;
    }
    for (i = 0; i < N; i++) {
        int req = GetRequest();
        int ans = 0;

        if(usea[req]) continue;

        for(int j = 0;j < logK;j++){
            ans *= 2;
            ans += A[cnt*logK + j];
        }

        usea[sh[ans]] = false;
        usea[req] = true;
        PutBack(sh[ans]);
        sh[ans] = req;
        cnt++;
    }
}

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