oj.uz

Submission #365013

# Submission time Handle Problem Language Result Execution time Memory
365013 2021-02-10T18:12:36 Z mjhmjh1104 Last supper (IOI12_supper) C++14
100 / 100
 162 ms 10040 KB 
#include "advisor.h"
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int nx[200006], color[100006];
bool res[200006];

void ComputeAdvice(int *c, int n, int k, int m) {
    vector<int> v;
    for (int i = 0; i < k; i++) v.push_back(i);
    for (int i = 0; i < n; i++) v.push_back(c[i]);
    for (int i = 0; i < n + k; i++) nx[i] = 2e9;
    for (int i = 0; i < n; i++) color[i] = -1;
    for (int i = 0; i < n + k; i++) {
        if (color[v[i]] != -1) nx[color[v[i]]] = i;
        color[v[i]] = i;
    }
    set<pair<int, int>> q;
    for (int i = 0; i < k; i++) q.insert({ nx[i], i });
    for (int i = k; i < n + k; i++) {
        auto it = q.lower_bound({ i, -1 });
        if (it == q.end() || it->first != i) {
            it = q.end();
            it--;
            res[it->second] = true;
        }
        q.erase(it);
        q.insert({ nx[i], i });
    }
    for (int i = 0; i < n + k; i++) WriteAdvice(res[i]);
}

#include "assistant.h"
#include <set>
#include <queue>
using namespace std;

int mem[200006];

void Assist(unsigned char *a, int n, int k, int r) {
    queue<int> v;
    set<int> s;
    for (int i = 0; i < k; i++) mem[i] = i;
    for (int i = 0; i < n + k; i++) if (a[i]) v.push(i);
    for (int i = 0; i < k; i++) s.insert(i);
    for (int i = 0; i < n; i++) {
        int c = GetRequest();
        mem[i + k] = c;
        if (!s.count(c)) {
            auto it = s.find(mem[v.front()]); v.pop();
            s.erase(it);
            PutBack(*it);
            s.insert(c);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 744 KB Output is correct
3 Correct 2 ms 916 KB Output is correct
4 Correct 4 ms 1192 KB Output is correct
5 Correct 4 ms 1072 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 5 ms 1072 KB Output is correct
8 Correct 6 ms 1200 KB Output is correct
9 Correct 6 ms 1072 KB Output is correct
10 Correct 7 ms 1204 KB Output is correct
11 Correct 6 ms 1200 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1452 KB Output is correct
2 Correct 57 ms 3912 KB Output is correct
3 Correct 153 ms 10040 KB Output is correct
4 Correct 79 ms 6376 KB Output is correct
5 Correct 100 ms 6452 KB Output is correct
6 Correct 115 ms 6828 KB Output is correct
7 Correct 142 ms 8096 KB Output is correct
8 Correct 117 ms 7772 KB Output is correct
9 Correct 73 ms 6412 KB Output is correct
10 Correct 139 ms 9368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7188 KB Output is correct
2 Correct 143 ms 8592 KB Output is correct
3 Correct 138 ms 8784 KB Output is correct
4 Correct 140 ms 8800 KB Output is correct
5 Correct 131 ms 7948 KB Output is correct
6 Correct 142 ms 8712 KB Output is correct
7 Correct 148 ms 8960 KB Output is correct
8 Correct 129 ms 8840 KB Output is correct
9 Correct 135 ms 8464 KB Output is correct
10 Correct 134 ms 8804 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1176 KB Output is correct
2 Correct 6 ms 1200 KB Output is correct
3 Correct 4 ms 944 KB Output is correct
4 Correct 5 ms 1072 KB Output is correct
5 Correct 5 ms 944 KB Output is correct
6 Correct 6 ms 1124 KB Output is correct
7 Correct 6 ms 1072 KB Output is correct
8 Correct 7 ms 1200 KB Output is correct
9 Correct 6 ms 1072 KB Output is correct
10 Correct 7 ms 1592 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8084 KB Output is correct - 120000 bits used
2 Correct 142 ms 8464 KB Output is correct - 122000 bits used
3 Correct 134 ms 8712 KB Output is correct - 125000 bits used
4 Correct 137 ms 8648 KB Output is correct - 125000 bits used
5 Correct 134 ms 8948 KB Output is correct - 125000 bits used
6 Correct 133 ms 8948 KB Output is correct - 125000 bits used
7 Correct 136 ms 8844 KB Output is correct - 124828 bits used
8 Correct 145 ms 9016 KB Output is correct - 124910 bits used
9 Correct 162 ms 8800 KB Output is correct - 125000 bits used
10 Correct 135 ms 8968 KB Output is correct - 125000 bits used