Submission #31143

#	Time	Username	Problem	Language	Result	Execution time	Memory
31143		cscandkswon	Last supper (IOI12_supper)	C++14	100 / 100	333 ms	145544 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
const int MAXN=100005;

deque<int> D[MAXN];
multimap<int, int> S;
unordered_set<int> U;
int A[MAXN];

void ComputeAdvice(int *C, int N, int K, int M) {
    int i;
    for(i=0; i<N; i++) D[C[i]].push_back(i);
    for(i=0; i<N; i++) D[i].push_back(N);
    for(i=0; i<K; i++) S.insert(make_pair(D[i].front(), i));
    for(i=0; i<K; i++) U.insert(i);
    for(i=0; i<N; i++){
        if(U.find(C[i])!=U.end()){
            A[i]=-1;
            S.erase(S.begin());
            D[C[i]].pop_front();
            S.insert(make_pair(D[C[i]].front(), C[i]));
        }
        else{
            pair<int, int> p=*(--S.end());
            S.erase(--S.end());
            A[i]=p.second;
            D[C[i]].pop_front();
            S.insert(make_pair(D[C[i]].front(), C[i]));
            U.erase(p.second);
            U.insert(C[i]);
        }
    }
    for(i=0; i<N; i++) D[i].clear();
    for(i=0; i<N; i++) D[C[i]].push_back(i);
    for(i=0; i<N; i++) D[i].push_back(N);
    for(i=0; i<K; i++){
        if(A[D[i].front()]==-1) WriteAdvice(1);
        else WriteAdvice(0);
    }
    for(i=0; i<N; i++){
        D[C[i]].pop_front();
        if(A[D[C[i]].front()]==-1) WriteAdvice(1);
        else WriteAdvice(0);
    }
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
const int MAXN=100005;

int X[MAXN], Y[MAXN];
unordered_set<int> P, Q;      // P:0, Q:1

void Assist(unsigned char *A, int N, int K, int R) {
    int i, rv, x;
    for(i=0; i<K; i++) X[i]=A[i];
    for(i=0; i<N; i++) Y[i]=A[K+i];
    for(i=0; i<K; i++){
        if(X[i]==0) P.insert(i);
        else Q.insert(i);
    }
    for(i=0; i<N; i++){
        rv=GetRequest();
        x=Y[i];
        if(P.find(rv)!=P.end()){
            if(x==1){
                P.erase(P.find(rv));
                Q.insert(rv);
            }
        }
        else if(Q.find(rv)!=Q.end()){
            if(x==0){
                Q.erase(Q.find(rv));
                P.insert(rv);
            }
        }
        else{
            PutBack(*P.begin());
            P.erase(P.begin());
            if(x==0) P.insert(rv);
            else Q.insert(rv);
        }
    }
}

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