oj.uz

Submission #986923

# Submission time Handle Problem Language Result Execution time Memory
986923 2024-05-21T15:02:05 Z Sharky Last supper (IOI12_supper) C++17
100 / 100
 184 ms 85440 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> req(N + K, 0);
    for (int i = 0; i < K; i++) req[i] = i;
    for (int i = K; i < N + K; i++) req[i] = C[i - K];
    vector<int> s(N + K, 0);
    vector<vector<int>> add(N), del(N);
    vector<queue<int>> pos(N);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < N + K; i++) {
        pos[req[i]].push(i);
        if (i < K) scaff[i] = true;
    }
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < N + K; i++) {
        if (!scaff[req[i]]) {
            auto [dist, col] = pq.top();
            pq.pop();
            del[col].push_back(i);
            scaff[col] = false;
            scaff[req[i]] = true;
        }
        pos[req[i]].pop();
        int tp = inf;
        if (!pos[req[i]].empty()) tp = pos[req[i]].front();
        pq.push({tp, req[i]});
        add[req[i]].push_back(i);
    }
    for (int i = 0; i < N; i++) del[i].push_back(N + K);
    for (int i = 0; i < N + K; i++) {
        auto it = upper_bound(add[req[i]].begin(), add[req[i]].end(), i);
        int k = *upper_bound(del[req[i]].begin(), del[req[i]].end(), i);
        if (it == add[req[i]].end() || (*it) > k) s[i] = 1;
        WriteAdvice(s[i]);
    }
}

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

void Assist(unsigned char *A, int N, int K, int R) {
    assert(R == N + K);
    vector<set<int>> st(2);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < K; i++) {
        st[A[i]].insert(i);
        scaff[i] = true;
    }
    for (int i = K; i < N + K; i++) {
        int req = GetRequest();
        if (!st[1].empty() && !scaff[req]) {
            int f = *st[1].begin();
            st[1].erase(f);
            PutBack(f);
            scaff[f] = false;
            scaff[req] = true;
        }
        st[0].erase(req);
        st[A[i]].insert(req);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 792 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 2 ms 1556 KB Output is correct
4 Correct 4 ms 3144 KB Output is correct
5 Correct 5 ms 4840 KB Output is correct
6 Correct 5 ms 4692 KB Output is correct
7 Correct 6 ms 4696 KB Output is correct
8 Correct 6 ms 5108 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 7 ms 4956 KB Output is correct
11 Correct 6 ms 4956 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8828 KB Output is correct
2 Correct 64 ms 41528 KB Output is correct
3 Correct 164 ms 85440 KB Output is correct
4 Correct 135 ms 81688 KB Output is correct
5 Correct 136 ms 81676 KB Output is correct
6 Correct 146 ms 82228 KB Output is correct
7 Correct 156 ms 83712 KB Output is correct
8 Correct 123 ms 71904 KB Output is correct
9 Correct 119 ms 79348 KB Output is correct
10 Correct 161 ms 84472 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 66428 KB Output is correct
2 Correct 159 ms 84148 KB Output is correct
3 Correct 155 ms 83972 KB Output is correct
4 Correct 156 ms 83888 KB Output is correct
5 Correct 143 ms 82288 KB Output is correct
6 Correct 154 ms 83892 KB Output is correct
7 Correct 184 ms 83876 KB Output is correct
8 Correct 147 ms 84572 KB Output is correct
9 Correct 138 ms 83256 KB Output is correct
10 Correct 156 ms 83892 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3900 KB Output is correct
2 Correct 6 ms 4964 KB Output is correct
3 Correct 5 ms 4708 KB Output is correct
4 Correct 5 ms 4708 KB Output is correct
5 Correct 8 ms 4788 KB Output is correct
6 Correct 6 ms 4960 KB Output is correct
7 Correct 6 ms 4708 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 7 ms 4964 KB Output is correct
10 Correct 8 ms 5228 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 82308 KB Output is correct - 120000 bits used
2 Correct 159 ms 82540 KB Output is correct - 122000 bits used
3 Correct 158 ms 82804 KB Output is correct - 125000 bits used
4 Correct 166 ms 82976 KB Output is correct - 125000 bits used
5 Correct 159 ms 82852 KB Output is correct - 125000 bits used
6 Correct 163 ms 82820 KB Output is correct - 125000 bits used
7 Correct 159 ms 82880 KB Output is correct - 124828 bits used
8 Correct 157 ms 82800 KB Output is correct - 124910 bits used
9 Correct 164 ms 82776 KB Output is correct - 125000 bits used
10 Correct 155 ms 83448 KB Output is correct - 125000 bits used