oj.uz

Submission #361946

# Submission time Handle Problem Language Result Execution time Memory
361946 2021-02-01T10:45:15 Z benedict0724 Last supper (IOI12_supper) C++17
40 / 100
 471 ms 81248 KB 
#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 logN = 0;
    while((1<<logN) <= N) logN++;

    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(shelf[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=logN-1;i>=0;i--){
            if((1<<i) & now) WriteAdvice(1);
            else WriteAdvice(0);
        }
    }
}

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

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

        if(usea[req]) continue;

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

        usea[ans] = false;
        usea[req] = true;

        PutBack(ans);
        cnt++;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 68440 KB Output is correct
2 Correct 49 ms 68068 KB Output is correct
3 Correct 49 ms 68068 KB Output is correct
4 Correct 65 ms 68260 KB Output is correct
5 Correct 66 ms 68704 KB Output is correct
6 Correct 63 ms 68456 KB Output is correct
7 Correct 52 ms 68488 KB Output is correct
8 Correct 63 ms 68580 KB Output is correct
9 Correct 62 ms 68576 KB Output is correct
10 Correct 60 ms 68644 KB Output is correct
11 Correct 66 ms 68280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 68924 KB Output is correct
2 Correct 152 ms 72200 KB Output is correct
3 Correct 356 ms 77768 KB Output is correct
4 Correct 471 ms 81248 KB Output is correct
5 Correct 456 ms 80732 KB Output is correct
6 Correct 396 ms 78640 KB Output is correct
7 Correct 311 ms 76864 KB Output is correct
8 Correct 328 ms 77300 KB Output is correct
9 Correct 453 ms 80600 KB Output is correct
10 Correct 271 ms 76528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 75100 KB Output is correct
2 Correct 290 ms 76448 KB Output is correct
3 Correct 292 ms 77636 KB Output is correct
4 Correct 268 ms 77320 KB Output is correct
5 Correct 231 ms 76084 KB Output is correct
6 Correct 288 ms 77384 KB Output is correct
7 Correct 281 ms 77948 KB Output is correct
8 Correct 387 ms 80488 KB Output is correct
9 Correct 218 ms 75728 KB Output is correct
10 Correct 295 ms 77640 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 68376 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 76820 KB Output is partially correct - 875347 bits used
2 Correct 303 ms 77012 KB Output is partially correct - 841041 bits used
3 Correct 305 ms 76632 KB Output is partially correct - 807466 bits used
4 Correct 287 ms 76656 KB Output is partially correct - 806939 bits used
5 Correct 284 ms 76484 KB Output is partially correct - 805358 bits used
6 Correct 286 ms 76480 KB Output is partially correct - 807109 bits used
7 Correct 288 ms 76296 KB Output is partially correct - 805902 bits used
8 Correct 286 ms 76428 KB Output is partially correct - 808452 bits used
9 Correct 285 ms 76672 KB Output is partially correct - 807874 bits used
10 Correct 387 ms 79260 KB Output is partially correct - 1266636 bits used