oj.uz

Submission #988872

# Submission time Handle Problem Language Result Execution time Memory
988872 2024-05-26T14:09:44 Z Ariadna Last supper (IOI12_supper) C++14
100 / 100
 65 ms 9800 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define pb push_back
 
using namespace std;
 
struct Segtree {
    int n;
    vector<pair<int, int>> st;
 
    Segtree(const vector<int>& a) {
        n = a.size();
        st = vector<pair<int, int>>(4*n);
        build(1, 0, n-1, a);
    }
 
    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) st[p] = {a[l], l};
        else {
            int m = (l+r)/2;
            build(2*p, l, m, a);
            build(2*p+1, m+1, r, a);
            if (st[2*p] > st[2*p+1]) st[p] = st[2*p];
            else st[p] = st[2*p+1];
        }
    }
 
    void change(int p, int l, int r, int i, int v) {
        if (l == r) st[p] = {v, i};
        else {
            int m = (l+r)/2;
            if (i <= m) change(2*p, l, m, i, v);
            else change(2*p+1, m+1, r, i, v);
            if (st[2*p] > st[2*p+1]) st[p] = st[2*p];
            else st[p] = st[2*p+1];
        }
    }
 
    pair<int, int> Max(int p, int l, int r, int i, int j) {
        if (i > j) return {0, -1};
        if (i == l && j == r) return st[p];
        int m = (l+r)/2;
        pair<int, int> a = Max(2*p, l, m, i, min(m, j));
        pair<int, int> b = Max(2*p+1, m+1, r, max(i, m+1), j);
        if (a.first > b.first) return a;
        return b;
    }
 
    void change(int i, int v) { change(1, 0, n-1, i, v); }
    int idx() { return Max(1, 0, n-1, 0, n-1).second; }
};

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> last_pos(N, N);
    vector<int> next_pos(N);
 
    for (int i = N-1; i >= 0; --i) {
        next_pos[i] = last_pos[C[i]]; 
        last_pos[C[i]] = i; 
    }
 
    vector<int> pos_on_scaffold(N, -1);
    for (int i = 0; i < K; ++i) pos_on_scaffold[i] = i;
 
    vector<int> scaffold(K);
    vector<int> next(K);
    for (int i = 0; i < K; ++i) {
        next[i] = last_pos[i];
        scaffold[i] = i;
    }
    Segtree Scaffold(next);
    vector<int> take(N);
    
    vector<int> optimal_strategy;
    for (int i = 0; i < N; ++i) {
        if (pos_on_scaffold[C[i]] != -1) {
            Scaffold.change(pos_on_scaffold[C[i]], next_pos[i]);
            take[i] = -1;
        } else {
            int idx = Scaffold.idx();
            optimal_strategy.pb(idx);
            Scaffold.change(idx, next_pos[i]);
            take[i] = scaffold[idx];
            pos_on_scaffold[scaffold[idx]] = -1;
            pos_on_scaffold[C[i]] = idx;
            scaffold[idx] = C[i];
        }
    }
    
    vector<int> time_taken(N, N); 
    vector<int> next_take(N); 
    for (int i = N-1; i >= 0; --i) {
        next_take[i] = time_taken[C[i]];
        if (take[i] != -1) {
            time_taken[take[i]] = i;
        }
    }

    for (int i = 0; i < K; ++i) {
        if (time_taken[i] < last_pos[i]) WriteAdvice(1);
        else WriteAdvice(0);
    }

    for (int i = 0; i < N; ++i) {
        if (next_take[i] < next_pos[i]) WriteAdvice(1);
        else WriteAdvice(0);
    }
}
#include "assistant.h"
#include <bits/stdc++.h>
 
using namespace std;

int GetRequest();
void PutBack(int c);
 
void Assist(unsigned char *A, int N, int K, int R) {
    unordered_set<int> scaffold, can_take;
    for (int i = 0; i < K; ++i) {
        scaffold.insert(i);
        if (A[i] == 1) can_take.insert(i);
    }

    for (int i = 0; i < N; ++i) {
        int c = GetRequest();
        if (scaffold.find(c) == scaffold.end()) {
            scaffold.insert(c);
            int color = *can_take.begin();
            can_take.erase(color);
            scaffold.erase(color);
            PutBack(color);
        }
        if (A[K+i] == 1) can_take.insert(c);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 780 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 4 ms 1104 KB Output is correct
7 Correct 3 ms 1088 KB Output is correct
8 Correct 3 ms 1104 KB Output is correct
9 Correct 3 ms 1104 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1104 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1680 KB Output is correct
2 Correct 25 ms 4156 KB Output is correct
3 Correct 53 ms 9800 KB Output is correct
4 Correct 47 ms 6544 KB Output is correct
5 Correct 40 ms 6540 KB Output is correct
6 Correct 48 ms 7244 KB Output is correct
7 Correct 56 ms 8336 KB Output is correct
8 Correct 41 ms 7828 KB Output is correct
9 Correct 38 ms 6388 KB Output is correct
10 Correct 56 ms 9508 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7168 KB Output is correct
2 Correct 56 ms 8976 KB Output is correct
3 Correct 55 ms 9076 KB Output is correct
4 Correct 59 ms 8984 KB Output is correct
5 Correct 54 ms 8360 KB Output is correct
6 Correct 61 ms 9020 KB Output is correct
7 Correct 56 ms 8984 KB Output is correct
8 Correct 49 ms 8720 KB Output is correct
9 Correct 46 ms 9220 KB Output is correct
10 Correct 65 ms 8952 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1096 KB Output is correct
2 Correct 2 ms 1188 KB Output is correct
3 Correct 3 ms 1092 KB Output is correct
4 Correct 2 ms 968 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 4 ms 988 KB Output is correct
7 Correct 3 ms 1100 KB Output is correct
8 Correct 3 ms 968 KB Output is correct
9 Correct 3 ms 1096 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8492 KB Output is correct - 120000 bits used
2 Correct 54 ms 8732 KB Output is correct - 122000 bits used
3 Correct 65 ms 8884 KB Output is correct - 125000 bits used
4 Correct 55 ms 8984 KB Output is correct - 125000 bits used
5 Correct 55 ms 8976 KB Output is correct - 125000 bits used
6 Correct 55 ms 8992 KB Output is correct - 125000 bits used
7 Correct 61 ms 8892 KB Output is correct - 124828 bits used
8 Correct 57 ms 8980 KB Output is correct - 124910 bits used
9 Correct 55 ms 8928 KB Output is correct - 125000 bits used
10 Correct 49 ms 8668 KB Output is correct - 125000 bits used