oj.uz

Submission #361943

# Submission time Handle Problem Language Result Execution time Memory
361943 2021-02-01T10:25:00 Z benedict0724 Last supper (IOI12_supper) C++17
20 / 100
 490 ms 83408 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 include[100000];
void ComputeAdvice(int *C, int N, int K, int M) {
    int logN = 0;
    while(N + 1 >= (1<<logN)) logN++;

    for(int i=0;i<N;i++) useWhen[C[i]].push(i);
    for(int i=0;i<K;i++) {
        shelf[i] = i; include[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(!include[C[i]]){
            int m = pq.top().second; pq.pop();

            include[shelf[m]] = false;
            include[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{
            ret.push((1<<logN) - 1);
            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"

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

        if(ans != (1<<logN) - 1) PutBack(ans);
    }
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:8:13: warning: unused variable 'req' [-Wunused-variable]
    8 |         int req = GetRequest();
      |             ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 68072 KB Output is correct
2 Correct 56 ms 68200 KB Output is correct
3 Correct 52 ms 68096 KB Output is correct
4 Correct 57 ms 68312 KB Output is correct
5 Correct 66 ms 68704 KB Output is correct
6 Correct 65 ms 68644 KB Output is correct
7 Correct 64 ms 68840 KB Output is correct
8 Correct 65 ms 68516 KB Output is correct
9 Correct 65 ms 68516 KB Output is correct
10 Correct 66 ms 68648 KB Output is correct
11 Correct 65 ms 68656 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 69616 KB Output is correct
2 Correct 241 ms 75144 KB Output is correct
3 Correct 447 ms 83012 KB Output is correct
4 Correct 473 ms 82616 KB Output is correct
5 Correct 490 ms 82620 KB Output is correct
6 Correct 479 ms 82964 KB Output is correct
7 Correct 462 ms 83048 KB Output is correct
8 Correct 401 ms 80652 KB Output is correct
9 Correct 443 ms 82176 KB Output is correct
10 Correct 443 ms 83336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 80160 KB Output is correct
2 Incorrect 106 ms 72792 KB Error - advice is too long
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
3.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 83248 KB Output is partially correct - 1700000 bits used
2 Correct 468 ms 83224 KB Output is partially correct - 1700000 bits used
3 Correct 453 ms 83408 KB Output is partially correct - 1700000 bits used
4 Correct 446 ms 83096 KB Output is partially correct - 1700000 bits used
5 Correct 454 ms 83248 KB Output is partially correct - 1700000 bits used
6 Correct 447 ms 83012 KB Output is partially correct - 1700000 bits used
7 Correct 450 ms 83084 KB Output is partially correct - 1697263 bits used
8 Correct 469 ms 83072 KB Output is partially correct - 1700000 bits used
9 Correct 451 ms 83104 KB Output is partially correct - 1700000 bits used
10 Correct 476 ms 82792 KB Output is partially correct - 1700000 bits used