oj.uz

Submission #157309

# Submission time Handle Problem Language Result Execution time Memory
157309 2019-10-10T14:27:50 Z dolphingarlic Last supper (IOI12_supper) C++14
100 / 100
 498 ms 152304 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

set<pair<int, int>> scaffold;
map<int, int> mp;
queue<int> occurrences[100000];
int swap_sequence[100000];
bool on_scaffold[100000], active[200000];

void ComputeAdvice(int *C, int N, int K, int M) {
    FOR(i, 0, N) occurrences[C[i]].push(i);
    FOR(i, 0, N) occurrences[i].push(INT_MAX);

    FOR(i, 0, K) {
        scaffold.insert({-occurrences[i].front(), i});
        on_scaffold[i] = true;
    }

    FOR(i, 0, N) {
        if (on_scaffold[C[i]]) {
            swap_sequence[i] = C[i];
            scaffold.erase({-occurrences[C[i]].front(), C[i]});
        } else {
            swap_sequence[i] = (*scaffold.begin()).second;
            on_scaffold[(*scaffold.begin()).second] = false;
            scaffold.erase(scaffold.begin());
        }
        occurrences[C[i]].pop();
        scaffold.insert({-occurrences[C[i]].front(), C[i]});
        on_scaffold[C[i]] = true;
    }

    FOR(i, 0, N) on_scaffold[i] = (i < K);

    FOR(i, 0, K) mp[i] = i;
    FOR(i, 0, N) {
        if (on_scaffold[C[i]]) {
            active[mp[C[i]]] = true;
        } else {
            on_scaffold[swap_sequence[i]] = false;
        }
        mp[C[i]] = i + K;
        on_scaffold[C[i]] = true;
    }

    FOR(i, 0, N + K) WriteAdvice(active[i]);
}

#include "assistant.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

set<pair<int, int>> scaffold;
int on_scaffold[100000];

void Assist(unsigned char *A, int N, int K, int R) {
    FOR(i, 0, K) {
        scaffold.insert({A[i], i});
        on_scaffold[i] = A[i] + 1;
    }

    FOR(i, K, N + K) {
        int nxt = GetRequest();
        if (on_scaffold[nxt]) {
            scaffold.erase({on_scaffold[nxt] - 1, nxt});
            scaffold.insert({A[i], nxt});
        } else {
            PutBack((*scaffold.begin()).second);
            on_scaffold[(*scaffold.begin()).second] = 0;
            scaffold.erase(scaffold.begin());
            scaffold.insert({A[i], nxt});
        }
        on_scaffold[nxt] = A[i] + 1;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 135152 KB Output is correct
2 Correct 73 ms 135408 KB Output is correct
3 Correct 74 ms 135408 KB Output is correct
4 Correct 76 ms 135664 KB Output is correct
5 Correct 77 ms 135864 KB Output is correct
6 Correct 89 ms 135920 KB Output is correct
7 Correct 80 ms 135544 KB Output is correct
8 Correct 79 ms 136432 KB Output is correct
9 Correct 81 ms 136184 KB Output is correct
10 Correct 84 ms 136024 KB Output is correct
11 Correct 100 ms 135920 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 136736 KB Output is correct
2 Correct 168 ms 140056 KB Output is correct
3 Correct 341 ms 151776 KB Output is correct
4 Correct 217 ms 146448 KB Output is correct
5 Correct 233 ms 146272 KB Output is correct
6 Correct 264 ms 147168 KB Output is correct
7 Correct 319 ms 148984 KB Output is correct
8 Correct 284 ms 149760 KB Output is correct
9 Correct 185 ms 140528 KB Output is correct
10 Correct 345 ms 150504 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 146624 KB Output is correct
2 Correct 337 ms 149360 KB Output is correct
3 Correct 350 ms 149864 KB Output is correct
4 Correct 345 ms 149176 KB Output is correct
5 Correct 327 ms 146672 KB Output is correct
6 Correct 498 ms 149488 KB Output is correct
7 Correct 397 ms 149432 KB Output is correct
8 Correct 358 ms 152304 KB Output is correct
9 Correct 364 ms 146888 KB Output is correct
10 Correct 341 ms 149608 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 135984 KB Output is correct
2 Correct 81 ms 136384 KB Output is correct
3 Correct 78 ms 135664 KB Output is correct
4 Correct 78 ms 135920 KB Output is correct
5 Correct 79 ms 135920 KB Output is correct
6 Correct 81 ms 135848 KB Output is correct
7 Correct 88 ms 135976 KB Output is correct
8 Correct 83 ms 136288 KB Output is correct
9 Correct 82 ms 136072 KB Output is correct
10 Correct 84 ms 136176 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 148864 KB Output is correct - 120000 bits used
2 Correct 331 ms 149272 KB Output is correct - 122000 bits used
3 Correct 337 ms 149608 KB Output is correct - 125000 bits used
4 Correct 344 ms 149784 KB Output is correct - 125000 bits used
5 Correct 334 ms 149496 KB Output is correct - 125000 bits used
6 Correct 334 ms 149816 KB Output is correct - 125000 bits used
7 Correct 328 ms 149488 KB Output is correct - 124828 bits used
8 Correct 324 ms 149744 KB Output is correct - 124910 bits used
9 Correct 334 ms 149488 KB Output is correct - 125000 bits used
10 Correct 305 ms 151704 KB Output is correct - 125000 bits used