oj.uz

Submission #153120

# Submission time Handle Problem Language Result Execution time Memory
153120 2019-09-12T13:29:52 Z popovicirobert Last supper (IOI12_supper) C++14
100 / 100
 212 ms 10196 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;


void ComputeAdvice(int *C, int n, int k, int M) {

    vector <int> last(n, n), nxt(n);
    int i;

    for(i = n - 1; i >= 0; i--) {
        nxt[i] = last[C[i]];
        last[C[i]] = i;
    }

    set < pair <int, int> > pq;
    vector <int> pos(n, -1);

    for(i = 0; i < k; i++) {
        pq.insert({last[i], i});
        pos[i] = i;
    }

    vector <unsigned char> sol(n + k, 0);
    for(i = 0; i < n; i++) {
        if(pos[C[i]] != -1) {
            sol[pos[C[i]]] = 1;
            pq.erase(pq.lower_bound({i, -1}));
        }
        else {
            int p = prev(pq.end()) -> second;
            if(p < k) {
                pos[p] = -1;
            }
            else {
                pos[C[p - k]] = -1;
            }
            pq.erase(prev(pq.end()));
        }
        pq.insert({nxt[i], i + k});
        pos[C[i]] = i + k;
        /*for(auto it : pq) {
            cerr << it.first << " " << it.second << "\n";
        }
        cerr << "\n";*/
    }

    for(auto it : sol) {
        WriteAdvice(it);
    }
}

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

void Assist(unsigned char *A, int n, int k, int R) {
    set <int> col, bad;
    int i;

    /*cerr << n + k << "\n";
    for(i = 0; i < n + k; i++) {
        cerr << (int) A[i] << " ";
    }*/

    for(i = 0; i < k; i++) {
        col.insert(i);
        if(A[i] == 0) {
            bad.insert(i);
        }
    }

    for(i = k; i < n + k; i++) {
        int cur = GetRequest();
        if(col.count(cur) == 0) {
            if(bad.size() == 0) {
                while(1) {

                }
            }
            PutBack(*bad.begin());
            col.erase(*bad.begin());
            bad.erase(bad.begin());
        }
        if(A[i] == 0) {
            bad.insert(cur);
        }
        col.insert(cur);
    }

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 764 KB Output is correct
2 Correct 4 ms 864 KB Output is correct
3 Correct 6 ms 892 KB Output is correct
4 Correct 8 ms 936 KB Output is correct
5 Correct 8 ms 1008 KB Output is correct
6 Correct 10 ms 1072 KB Output is correct
7 Correct 11 ms 1300 KB Output is correct
8 Correct 11 ms 1112 KB Output is correct
9 Correct 11 ms 1200 KB Output is correct
10 Correct 12 ms 1352 KB Output is correct
11 Correct 11 ms 1200 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1520 KB Output is correct
2 Correct 73 ms 3636 KB Output is correct
3 Correct 201 ms 10196 KB Output is correct
4 Correct 97 ms 5360 KB Output is correct
5 Correct 107 ms 5360 KB Output is correct
6 Correct 142 ms 5880 KB Output is correct
7 Correct 191 ms 7872 KB Output is correct
8 Correct 151 ms 7952 KB Output is correct
9 Correct 87 ms 5360 KB Output is correct
10 Correct 212 ms 9360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 6956 KB Output is correct
2 Correct 190 ms 8580 KB Output is correct
3 Correct 192 ms 8728 KB Output is correct
4 Correct 192 ms 8676 KB Output is correct
5 Correct 174 ms 8092 KB Output is correct
6 Correct 193 ms 8588 KB Output is correct
7 Correct 200 ms 8644 KB Output is correct
8 Correct 169 ms 8896 KB Output is correct
9 Correct 168 ms 8916 KB Output is correct
10 Correct 192 ms 8740 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1188 KB Output is correct
2 Correct 12 ms 1200 KB Output is correct
3 Correct 10 ms 1068 KB Output is correct
4 Correct 7 ms 1264 KB Output is correct
5 Correct 10 ms 1028 KB Output is correct
6 Correct 10 ms 1016 KB Output is correct
7 Correct 10 ms 1068 KB Output is correct
8 Correct 10 ms 1116 KB Output is correct
9 Correct 10 ms 1196 KB Output is correct
10 Correct 14 ms 1596 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 7876 KB Output is correct - 120000 bits used
2 Correct 181 ms 8308 KB Output is correct - 122000 bits used
3 Correct 189 ms 8648 KB Output is correct - 125000 bits used
4 Correct 195 ms 8604 KB Output is correct - 125000 bits used
5 Correct 190 ms 8464 KB Output is correct - 125000 bits used
6 Correct 202 ms 8696 KB Output is correct - 125000 bits used
7 Correct 191 ms 8532 KB Output is correct - 124828 bits used
8 Correct 199 ms 8732 KB Output is correct - 124910 bits used
9 Correct 194 ms 8540 KB Output is correct - 125000 bits used
10 Correct 178 ms 8828 KB Output is correct - 125000 bits used