oj.uz

Submission #361969

# Submission time Handle Problem Language Result Execution time Memory
361969 2021-02-01T12:22:35 Z benedict0724 Last supper (IOI12_supper) C++17
43 / 100
 368 ms 79712 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 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);
        }
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 52 ms 68312 KB Output is correct
2 Correct 54 ms 68200 KB Output is correct
3 Correct 55 ms 68072 KB Output is correct
4 Correct 56 ms 68244 KB Output is correct
5 Correct 56 ms 68516 KB Output is correct
6 Correct 72 ms 68304 KB Output is correct
7 Correct 57 ms 68416 KB Output is correct
8 Correct 67 ms 68324 KB Output is correct
9 Correct 63 ms 68456 KB Output is correct
10 Correct 60 ms 68416 KB Output is correct
11 Correct 65 ms 68296 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 69068 KB Output is correct
2 Correct 138 ms 72052 KB Output is correct
3 Correct 318 ms 78948 KB Output is correct
4 Correct 252 ms 75948 KB Output is correct
5 Correct 310 ms 78108 KB Output is correct
6 Correct 312 ms 78216 KB Output is correct
7 Correct 291 ms 77488 KB Output is correct
8 Correct 293 ms 77656 KB Output is correct
9 Correct 189 ms 74700 KB Output is correct
10 Correct 254 ms 77112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 75532 KB Output is correct
2 Correct 271 ms 77088 KB Output is correct
3 Correct 268 ms 77368 KB Output is correct
4 Correct 256 ms 76796 KB Output is correct
5 Correct 214 ms 75620 KB Output is correct
6 Correct 288 ms 77328 KB Output is correct
7 Correct 262 ms 77176 KB Output is correct
8 Correct 349 ms 79564 KB Output is correct
9 Correct 205 ms 75260 KB Output is correct
10 Correct 295 ms 77068 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 77452 KB Output is partially correct - 772365 bits used
2 Correct 289 ms 77996 KB Output is partially correct - 742095 bits used
3 Correct 266 ms 77068 KB Output is partially correct - 712470 bits used
4 Correct 273 ms 77420 KB Output is partially correct - 712005 bits used
5 Correct 272 ms 77088 KB Output is partially correct - 710610 bits used
6 Correct 266 ms 77068 KB Output is partially correct - 712155 bits used
7 Correct 266 ms 77088 KB Output is partially correct - 711090 bits used
8 Correct 272 ms 77244 KB Output is partially correct - 713340 bits used
9 Correct 269 ms 77084 KB Output is partially correct - 712830 bits used
10 Correct 368 ms 79712 KB Output is partially correct - 1117620 bits used