oj.uz

Submission #361967

# Submission time Handle Problem Language Result Execution time Memory
361967 2021-02-01T12:13:54 Z benedict0724 Last supper (IOI12_supper) C++17
0 / 100
 353 ms 80004 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 location[100000], 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[ans] = false;
        usea[req] = true;
        PutBack(sh[ans]);
        sh[ans] = req;
        cnt++;
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 68320 KB Output is correct
2 Correct 52 ms 68072 KB Output is correct
3 Correct 53 ms 68072 KB Output is correct
4 Incorrect 57 ms 68116 KB Error - Not putting back color when it is not on the scaffold
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 68796 KB Error - Not putting back color when it is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 75540 KB Output is correct
2 Correct 267 ms 77236 KB Output is correct
3 Correct 267 ms 77088 KB Output is correct
4 Correct 250 ms 76884 KB Output is correct
5 Incorrect 236 ms 75420 KB Error - Not putting back color when it is not on the scaffold
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 282 ms 77608 KB Error - Not putting back color when it is not on the scaffold
2 Correct 268 ms 77300 KB Output is partially correct - 742095 bits used
3 Correct 282 ms 77440 KB Output is partially correct - 712470 bits used
4 Correct 291 ms 77472 KB Output is partially correct - 712005 bits used
5 Correct 261 ms 77212 KB Output is partially correct - 710610 bits used
6 Correct 300 ms 77068 KB Output is partially correct - 712155 bits used
7 Correct 276 ms 77256 KB Output is partially correct - 711090 bits used
8 Correct 267 ms 77556 KB Output is partially correct - 713340 bits used
9 Correct 270 ms 77068 KB Output is partially correct - 712830 bits used
10 Incorrect 353 ms 80004 KB Error - Not putting back color when it is not on the scaffold