oj.uz

Submission #551358

# Submission time Handle Problem Language Result Execution time Memory
551358 2022-04-20T13:38:40 Z elazarkoren Last supper (IOI12_supper) C++17
100 / 100
 186 ms 13276 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 1e5 + 5;
const int infinity = 1e9;

vi ind[MAX_N];

void ComputeAdvice(int *c, int n, int k, int m) {
    vb bits(k + n, 1);
    set<pii, greater<pii>> s;
    for (int i = 0; i < k; i++) {
        ind[i].push_back(i);
    }
    for (int i = 0; i < n; i++) ind[c[i]].push_back(i + k);
    for (int i = 0; i < n; i++) ind[i].push_back(infinity);
    for (int i = 0; i < k; i++) {
        s.insert({ind[i][1], i});
    }
    for (int i = k; i < n + k; i++) {
        int x = c[i - k];
        if (s.count({i, x})) {
            s.erase(s.find({i, x}));
        } else {
            auto [j, y] = *s.begin();
            s.erase({j, y});
            auto it = lower_bound(all(ind[y]), j);
            it--;
            bits[*it] = 0;
        }
        auto it = upper_bound(all(ind[x]), i);
        s.insert({*it, x});
    }
    for (int i = 0; i < n + k; i++) {
        WriteAdvice(bits[i]);
    }
}
//4 2 65000
//2 0 3 0

//6 3 1000
//1 2 4 3 0 3
#include "assistant.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

void Assist(unsigned char *a, int n, int k, int r) {
    vb bits(n + k);
    for (int i = 0; i < r; i++) bits[i] = a[i];
    set<int> s;
    queue<int> q;
    for (int i = 0; i < k; i++) {
        s.insert(i);
        if (!bits[i]) q.push(i);
    }
    for (int i = k; i < n + k; i++) {
        int req = GetRequest();
        if (!s.count(req)) {
            PutBack(q.front());
            s.erase(s.find(q.front()));
            q.pop();
        }
        s.insert(req);
        if (!bits[i]) q.push(req);
    }
    return;
}
//4 2 65000
//2 0 3 0

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2948 KB Output is correct
2 Correct 2 ms 2948 KB Output is correct
3 Correct 4 ms 3220 KB Output is correct
4 Correct 4 ms 3120 KB Output is correct
5 Correct 5 ms 3164 KB Output is correct
6 Correct 6 ms 3260 KB Output is correct
7 Correct 7 ms 3388 KB Output is correct
8 Correct 9 ms 3420 KB Output is correct
9 Correct 7 ms 3404 KB Output is correct
10 Correct 7 ms 3404 KB Output is correct
11 Correct 8 ms 3424 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3784 KB Output is correct
2 Correct 57 ms 6848 KB Output is correct
3 Correct 156 ms 13276 KB Output is correct
4 Correct 96 ms 9836 KB Output is correct
5 Correct 91 ms 9828 KB Output is correct
6 Correct 119 ms 10484 KB Output is correct
7 Correct 138 ms 11960 KB Output is correct
8 Correct 108 ms 11212 KB Output is correct
9 Correct 79 ms 10392 KB Output is correct
10 Correct 142 ms 12920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 9728 KB Output is correct
2 Correct 135 ms 12296 KB Output is correct
3 Correct 142 ms 12480 KB Output is correct
4 Correct 165 ms 12512 KB Output is correct
5 Correct 123 ms 12048 KB Output is correct
6 Correct 186 ms 12480 KB Output is correct
7 Correct 174 ms 12476 KB Output is correct
8 Correct 129 ms 12268 KB Output is correct
9 Correct 137 ms 12880 KB Output is correct
10 Correct 155 ms 12444 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3348 KB Output is correct
2 Correct 7 ms 3372 KB Output is correct
3 Correct 6 ms 3260 KB Output is correct
4 Correct 5 ms 3260 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 6 ms 3272 KB Output is correct
7 Correct 7 ms 3304 KB Output is correct
8 Correct 6 ms 3412 KB Output is correct
9 Correct 7 ms 3388 KB Output is correct
10 Correct 9 ms 3664 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 10824 KB Output is correct - 120000 bits used
2 Correct 139 ms 10996 KB Output is correct - 122000 bits used
3 Correct 165 ms 11288 KB Output is correct - 125000 bits used
4 Correct 142 ms 11304 KB Output is correct - 125000 bits used
5 Correct 162 ms 11260 KB Output is correct - 125000 bits used
6 Correct 137 ms 11320 KB Output is correct - 125000 bits used
7 Correct 137 ms 11236 KB Output is correct - 124828 bits used
8 Correct 147 ms 11332 KB Output is correct - 124910 bits used
9 Correct 134 ms 11368 KB Output is correct - 125000 bits used
10 Correct 136 ms 11132 KB Output is correct - 125000 bits used