oj.uz

Submission #31143

# Submission time Handle Problem Language Result Execution time Memory
31143 2017-08-11T12:09:09 Z cscandkswon Last supper (IOI12_supper) C++14
100 / 100
 333 ms 145544 KB 
#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);
    }
}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 135408 KB Output is correct
2 Correct 77 ms 135848 KB Output is correct
3 Correct 70 ms 136080 KB Output is correct
4 Correct 76 ms 136080 KB Output is correct
5 Correct 75 ms 136080 KB Output is correct
6 Correct 73 ms 136080 KB Output is correct
7 Correct 75 ms 136080 KB Output is correct
8 Correct 74 ms 136160 KB Output is correct
9 Correct 74 ms 136160 KB Output is correct
10 Correct 75 ms 136184 KB Output is correct
11 Correct 78 ms 136184 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 136384 KB Output is correct
2 Correct 164 ms 138232 KB Output is correct
3 Correct 333 ms 145544 KB Output is correct
4 Correct 271 ms 145544 KB Output is correct
5 Correct 283 ms 145544 KB Output is correct
6 Correct 288 ms 145544 KB Output is correct
7 Correct 299 ms 145544 KB Output is correct
8 Correct 283 ms 145544 KB Output is correct
9 Correct 228 ms 145544 KB Output is correct
10 Correct 332 ms 145544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 145544 KB Output is correct
2 Correct 325 ms 145544 KB Output is correct
3 Correct 297 ms 145544 KB Output is correct
4 Correct 285 ms 145544 KB Output is correct
5 Correct 276 ms 145544 KB Output is correct
6 Correct 294 ms 145544 KB Output is correct
7 Correct 297 ms 145544 KB Output is correct
8 Correct 307 ms 145544 KB Output is correct
9 Correct 253 ms 145544 KB Output is correct
10 Correct 291 ms 145544 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 145544 KB Output is correct
2 Correct 65 ms 145544 KB Output is correct
3 Correct 66 ms 145544 KB Output is correct
4 Correct 81 ms 145544 KB Output is correct
5 Correct 67 ms 145544 KB Output is correct
6 Correct 68 ms 145544 KB Output is correct
7 Correct 69 ms 145544 KB Output is correct
8 Correct 66 ms 145544 KB Output is correct
9 Correct 67 ms 145544 KB Output is correct
10 Correct 68 ms 145544 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 145544 KB Output is correct - 120000 bits used
2 Correct 289 ms 145544 KB Output is correct - 122000 bits used
3 Correct 286 ms 145544 KB Output is correct - 125000 bits used
4 Correct 277 ms 145544 KB Output is correct - 125000 bits used
5 Correct 280 ms 145544 KB Output is correct - 125000 bits used
6 Correct 290 ms 145544 KB Output is correct - 125000 bits used
7 Correct 303 ms 145544 KB Output is correct - 124828 bits used
8 Correct 306 ms 145544 KB Output is correct - 124910 bits used
9 Correct 302 ms 145544 KB Output is correct - 125000 bits used
10 Correct 284 ms 145544 KB Output is correct - 125000 bits used