oj.uz

Submission #122193

# Submission time Handle Problem Language Result Execution time Memory
122193 2019-06-27T19:45:23 Z Osama_Alkhodairy Last supper (IOI12_supper) C++17
100 / 100
 210 ms 10080 KB 
#include <bits/stdc++.h>
#include "advisor.h"
//~ #include "grader.cpp"
using namespace std;

void ComputeAdvice(int *C, int N, int K, int M) {
    vector <int> las(N, N);
    vector <int> nex(N);
    for(int i = N - 1 ; i >= 0 ; i--){
        nex[i] = las[C[i]];
        las[C[i]] = i;
    }
    set <pair <int, int> > ready;
    for(int i = 0 ; i < K ; i++){
        ready.insert(make_pair(las[i], i));
    }
    vector <int> p(N);
    for(int i = 0 ; i < N ; i++){
        if(ready.count(make_pair(i, C[i]))){
            ready.erase(ready.find(make_pair(i, C[i])));
            ready.insert(make_pair(nex[i], C[i]));
            continue;
        }
        ready.erase(--ready.end());
        ready.insert(make_pair(nex[i], C[i]));
        p[i] = 1;
    }
    int optimal = 0;
    for(auto &i : p) optimal += i;
    for(int i = 0 ; i < K ; i++){
        if(las[i] == N) WriteAdvice(1);
        else WriteAdvice(p[las[i]]);
    }
    for(int i = 0 ; i < N ; i++){
        if(nex[i] == N) WriteAdvice(1);
        else WriteAdvice(p[nex[i]]);
    }
}

#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
    int pulls = 0;
    set <int> ready, passive;
    for(int i = 0 ; i < K ; i++){
        if(A[i] == 1) passive.insert(i);
        ready.insert(i);
    }
    for(int i = 0 ; i < N ; i++){
        int x = GetRequest();
        if(ready.count(x) == 0){
            int put = *passive.begin();
            PutBack(put);
            passive.erase(put);
            pulls++;
            ready.erase(put);
            ready.insert(x);
        }
        if(A[K + i] == 1) passive.insert(x);
        else passive.erase(x);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 776 KB Output is correct
2 Correct 4 ms 880 KB Output is correct
3 Correct 5 ms 944 KB Output is correct
4 Correct 6 ms 792 KB Output is correct
5 Correct 6 ms 928 KB Output is correct
6 Correct 8 ms 1180 KB Output is correct
7 Correct 7 ms 1064 KB Output is correct
8 Correct 9 ms 1136 KB Output is correct
9 Correct 8 ms 1036 KB Output is correct
10 Correct 10 ms 1208 KB Output is correct
11 Correct 9 ms 1184 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1356 KB Output is correct
2 Correct 57 ms 3272 KB Output is correct
3 Correct 172 ms 10080 KB Output is correct
4 Correct 78 ms 5104 KB Output is correct
5 Correct 90 ms 5104 KB Output is correct
6 Correct 116 ms 5832 KB Output is correct
7 Correct 150 ms 7632 KB Output is correct
8 Correct 120 ms 7636 KB Output is correct
9 Correct 72 ms 5104 KB Output is correct
10 Correct 164 ms 9268 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 6156 KB Output is correct
2 Correct 159 ms 8268 KB Output is correct
3 Correct 169 ms 8436 KB Output is correct
4 Correct 157 ms 8524 KB Output is correct
5 Correct 147 ms 7612 KB Output is correct
6 Correct 166 ms 8516 KB Output is correct
7 Correct 210 ms 8644 KB Output is correct
8 Correct 142 ms 8444 KB Output is correct
9 Correct 134 ms 8576 KB Output is correct
10 Correct 164 ms 8528 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1188 KB Output is correct
2 Correct 8 ms 1184 KB Output is correct
3 Correct 7 ms 928 KB Output is correct
4 Correct 8 ms 800 KB Output is correct
5 Correct 8 ms 1060 KB Output is correct
6 Correct 7 ms 796 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 9 ms 1164 KB Output is correct
9 Correct 10 ms 1124 KB Output is correct
10 Correct 12 ms 1508 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 6808 KB Output is correct - 120000 bits used
2 Correct 157 ms 6992 KB Output is correct - 122000 bits used
3 Correct 210 ms 7360 KB Output is correct - 125000 bits used
4 Correct 160 ms 7588 KB Output is correct - 125000 bits used
5 Correct 159 ms 7360 KB Output is correct - 125000 bits used
6 Correct 160 ms 7452 KB Output is correct - 125000 bits used
7 Correct 159 ms 7588 KB Output is correct - 124828 bits used
8 Correct 160 ms 7468 KB Output is correct - 124910 bits used
9 Correct 160 ms 7344 KB Output is correct - 125000 bits used
10 Correct 146 ms 7320 KB Output is correct - 125000 bits used