oj.uz

Submission #431138

# Submission time Handle Problem Language Result Execution time Memory
431138 2021-06-17T09:57:49 Z KoD Last supper (IOI12_supper) C++17
100 / 100
 314 ms 73292 KB 
#include <bits/stdc++.h>
#include "advisor.h"

template <class T> using Vec = std::vector<T>;

void ComputeAdvice(int *C, int N, int K, int M) {
    Vec<std::queue<int>> appear(N);
    for (int i = 0; i < N; ++i) {
        appear[C[i]].push(i);
    }
    for (int i = 0; i < N; ++i) {
        appear[i].push(N);
    }
    std::set<std::pair<int, int>> heap;
    Vec<int> when(N, -2);
    for (int i = 0; i < K; ++i) {
        heap.emplace(appear[i].front(), i);
        when[i] = -1;
    }
    Vec<char> send(N + K);
    for (int i = 0; i < N; ++i) {
        if (when[C[i]] == -2) {
            assert(!heap.empty());
            const int k = heap.rbegin() -> second;
            heap.erase(std::prev(heap.end()));
            if (when[k] == -1) {
                send[k] = true;
            } else {
                send[K + when[k]] = true;
            }
            when[k] = -2;
        } else {
            heap.erase(std::make_pair(appear[C[i]].front(), C[i]));
        }
        appear[C[i]].pop();
        heap.emplace(appear[C[i]].front(), C[i]);
        when[C[i]] = i;
    }
    for (const auto x : send) {
        WriteAdvice(x);
    }
}

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

template <class T> using Vec = std::vector<T>;

void Assist(unsigned char *A, int N, int K, int R) {
    Vec<char> has(N);
    std::queue<int> dispose;
    for (int i = 0; i < K; ++i) {
        has[i] = true;
        if (A[i]) {
            dispose.push(i);
        }
    }
    for (int i = 0; i < N; ++i) {
        const int k = GetRequest();
        if (!has[k]) {
            assert(!dispose.empty());
            PutBack(dispose.front());
            has[dispose.front()] = false;
            dispose.pop();
            has[k] = true;
        }
        if (A[K + i]) {
            dispose.push(k);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 484 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 3 ms 1260 KB Output is correct
4 Correct 5 ms 2584 KB Output is correct
5 Correct 6 ms 3992 KB Output is correct
6 Correct 9 ms 4012 KB Output is correct
7 Correct 10 ms 4020 KB Output is correct
8 Correct 10 ms 4012 KB Output is correct
9 Correct 13 ms 4016 KB Output is correct
10 Correct 9 ms 4152 KB Output is correct
11 Correct 9 ms 4144 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7680 KB Output is correct
2 Correct 86 ms 36400 KB Output is correct
3 Correct 212 ms 73292 KB Output is correct
4 Correct 164 ms 71472 KB Output is correct
5 Correct 172 ms 71364 KB Output is correct
6 Correct 195 ms 71728 KB Output is correct
7 Correct 219 ms 72436 KB Output is correct
8 Correct 188 ms 61920 KB Output is correct
9 Correct 136 ms 70124 KB Output is correct
10 Correct 215 ms 72920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 57556 KB Output is correct
2 Correct 204 ms 72780 KB Output is correct
3 Correct 209 ms 72764 KB Output is correct
4 Correct 314 ms 72656 KB Output is correct
5 Correct 203 ms 71716 KB Output is correct
6 Correct 212 ms 72752 KB Output is correct
7 Correct 210 ms 72776 KB Output is correct
8 Correct 204 ms 72720 KB Output is correct
9 Correct 243 ms 72680 KB Output is correct
10 Correct 232 ms 72692 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3356 KB Output is correct
2 Correct 8 ms 4152 KB Output is correct
3 Correct 12 ms 4068 KB Output is correct
4 Correct 11 ms 4144 KB Output is correct
5 Correct 7 ms 3984 KB Output is correct
6 Correct 9 ms 4016 KB Output is correct
7 Correct 7 ms 4120 KB Output is correct
8 Correct 8 ms 4116 KB Output is correct
9 Correct 12 ms 4088 KB Output is correct
10 Correct 15 ms 4284 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 71256 KB Output is correct - 120000 bits used
2 Correct 194 ms 71432 KB Output is correct - 122000 bits used
3 Correct 193 ms 71516 KB Output is correct - 125000 bits used
4 Correct 211 ms 71600 KB Output is correct - 125000 bits used
5 Correct 219 ms 71508 KB Output is correct - 125000 bits used
6 Correct 200 ms 71620 KB Output is correct - 125000 bits used
7 Correct 223 ms 71520 KB Output is correct - 124828 bits used
8 Correct 198 ms 71660 KB Output is correct - 124910 bits used
9 Correct 261 ms 71448 KB Output is correct - 125000 bits used
10 Correct 183 ms 71536 KB Output is correct - 125000 bits used