oj.uz

Submission #362235

# Submission time Handle Problem Language Result Execution time Memory
362235 2021-02-02T10:12:17 Z benedict0724 Last supper (IOI12_supper) C++17
100 / 100
 168 ms 74072 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;
pair<int, int> shelf[100000]; int loc[100000];
bool use[100000], initial[100000], removable[100000];
void ComputeAdvice(int *C, int N, int K, int M) {

    for(int i=0;i<N;i++) useWhen[C[i]].push(i);
    for(int i=0;i<K;i++) {
        shelf[i] = {i, -1}; 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].first] = false;
            use[C[i]] = true;
            loc[C[i]] = m;

            shelf[m] = {C[i], i};
            useWhen[C[i]].pop();

            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]]});

            if(shelf[loc[C[i]]].second != -1)
                removable[shelf[loc[C[i]]].second] = true;
            else
                initial[C[i]] = true;

            shelf[loc[C[i]]].second = i;
        }
    }

    for(int i=0;i<K;i++){
        WriteAdvice(initial[i]);
    }
    for(int i=0;i<N;i++){
        WriteAdvice(removable[i]);
    }
}

#include "assistant.h"
#include <queue>
std::queue<int> toRemove; bool Using[100000];

void Assist(unsigned char *A, int N, int K, int R) {
    for(int i=0;i<K;i++){
        if(!A[i]) toRemove.push(i);
        Using[i] = true;
    }
    for(int i=0;i<N;i++){
        int req = GetRequest();
        if(Using[req]){
            if(!A[K + i]) toRemove.push(req);
            continue;
        }

        int rem = toRemove.front(); toRemove.pop();

        Using[rem] = false;
        Using[req] = true;

        if(!A[K + i]) toRemove.push(req);
        PutBack(rem);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 68300 KB Output is correct
2 Correct 53 ms 68200 KB Output is correct
3 Correct 53 ms 68080 KB Output is correct
4 Correct 54 ms 68232 KB Output is correct
5 Correct 57 ms 68424 KB Output is correct
6 Correct 58 ms 68256 KB Output is correct
7 Correct 56 ms 68404 KB Output is correct
8 Correct 57 ms 68516 KB Output is correct
9 Correct 56 ms 68496 KB Output is correct
10 Correct 58 ms 68636 KB Output is correct
11 Correct 58 ms 68256 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 68864 KB Output is correct
2 Correct 95 ms 70956 KB Output is correct
3 Correct 152 ms 73864 KB Output is correct
4 Correct 160 ms 72688 KB Output is correct
5 Correct 142 ms 72648 KB Output is correct
6 Correct 146 ms 73060 KB Output is correct
7 Correct 148 ms 73580 KB Output is correct
8 Correct 135 ms 72740 KB Output is correct
9 Correct 133 ms 72660 KB Output is correct
10 Correct 153 ms 74072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 72912 KB Output is correct
2 Correct 151 ms 73948 KB Output is correct
3 Correct 148 ms 73716 KB Output is correct
4 Correct 152 ms 73856 KB Output is correct
5 Correct 143 ms 73696 KB Output is correct
6 Correct 149 ms 73844 KB Output is correct
7 Correct 147 ms 73844 KB Output is correct
8 Correct 148 ms 73488 KB Output is correct
9 Correct 168 ms 74032 KB Output is correct
10 Correct 150 ms 74052 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68248 KB Output is correct
2 Correct 59 ms 68576 KB Output is correct
3 Correct 56 ms 68400 KB Output is correct
4 Correct 56 ms 68508 KB Output is correct
5 Correct 56 ms 68492 KB Output is correct
6 Correct 58 ms 68272 KB Output is correct
7 Correct 58 ms 68272 KB Output is correct
8 Correct 67 ms 68588 KB Output is correct
9 Correct 57 ms 68700 KB Output is correct
10 Correct 57 ms 68536 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 73580 KB Output is correct - 120000 bits used
2 Correct 149 ms 73712 KB Output is correct - 122000 bits used
3 Correct 154 ms 73916 KB Output is correct - 125000 bits used
4 Correct 154 ms 73716 KB Output is correct - 125000 bits used
5 Correct 149 ms 73928 KB Output is correct - 125000 bits used
6 Correct 148 ms 73872 KB Output is correct - 125000 bits used
7 Correct 148 ms 73932 KB Output is correct - 124828 bits used
8 Correct 151 ms 73812 KB Output is correct - 124910 bits used
9 Correct 151 ms 73924 KB Output is correct - 125000 bits used
10 Correct 155 ms 73708 KB Output is correct - 125000 bits used