oj.uz

Submission #586782

# Submission time Handle Problem Language Result Execution time Memory
586782 2022-06-30T17:03:02 Z keta_tsimakuridze Last supper (IOI12_supper) C++14
100 / 100
 251 ms 25432 KB 
#include "advisor.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second

using namespace std;
const int Nn = 1e5 + 5;
set<int> s[Nn];
void ComputeAdvice(int *c, int N, int K, int M) {
    for(int i = 0; i < N; i++) s[c[i]].insert(i + K), s[i].insert(N + K + 1);
    for(int i = 0; i < K; i++) s[i].insert(i);
    set<int> on;
    vector<int> f(N + K);
    set<pair<int,int> > cur;
    for(int i = 0; i < K; i++) {
        cur.insert({*s[i].upper_bound(i), i});
        on.insert(i);
    }
    int ans = 0;
    for(int i = K; i < N + K; i++) {
        int x = c[i - K];
        if(on.count(x)) {
            cur.erase({i, *--s[x].upper_bound(i - 1)});
            cur.insert({*s[x].upper_bound(i), i});
            continue;
        }
        ++ans;
        pii p = *--cur.end();
        cur.erase(p);
        f[p.s] = 1;
        if(p.s < K) {
            on.erase(p.s);
        } else on.erase(c[p.s - K]);
        on.insert(x);
        cur.insert({*s[x].upper_bound(i), i});
    }
    for(int i = 0; i < N + K; i++) WriteAdvice(f[i]);
  //  cout<< "advisoris" << ans << endl;
}

#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
void Assist(unsigned char *A, int N, int K, int R) {
    set<int> s, on;
    for(int i = 0; i < K; i++) {
            if(A[i] == 1) s.insert(i);
            on.insert(i);
    }
    int ans = 0;
    for(int i = K; i < N + K; i++) {
        int x = GetRequest();
        if(on.count(x)) {
            if(A[i]) s.insert(x);
            continue;
        }
        ++ans;
        if(s.size()) {
            int a = *s.begin();
            PutBack(a);
            on.erase(a);
            s.erase(a);
        } else {
            int a = *on.begin();
            PutBack(a);
            on.erase(a);
        }
        if(A[i]) s.insert(x);
        on.insert(x);
    }
    //cout << "assistantis " << ans << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5256 KB Output is correct
2 Correct 3 ms 5264 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 6 ms 5680 KB Output is correct
5 Correct 7 ms 5828 KB Output is correct
6 Correct 8 ms 5964 KB Output is correct
7 Correct 9 ms 6044 KB Output is correct
8 Correct 10 ms 6212 KB Output is correct
9 Correct 11 ms 6088 KB Output is correct
10 Correct 11 ms 6300 KB Output is correct
11 Correct 13 ms 6132 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7012 KB Output is correct
2 Correct 77 ms 12696 KB Output is correct
3 Correct 230 ms 25432 KB Output is correct
4 Correct 158 ms 18628 KB Output is correct
5 Correct 147 ms 18468 KB Output is correct
6 Correct 200 ms 19688 KB Output is correct
7 Correct 214 ms 22564 KB Output is correct
8 Correct 207 ms 20988 KB Output is correct
9 Correct 148 ms 18288 KB Output is correct
10 Correct 241 ms 24588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 18756 KB Output is correct
2 Correct 246 ms 23372 KB Output is correct
3 Correct 225 ms 23640 KB Output is correct
4 Correct 244 ms 23636 KB Output is correct
5 Correct 197 ms 22832 KB Output is correct
6 Correct 231 ms 23756 KB Output is correct
7 Correct 240 ms 23776 KB Output is correct
8 Correct 251 ms 23312 KB Output is correct
9 Correct 186 ms 24052 KB Output is correct
10 Correct 222 ms 23580 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6060 KB Output is correct
2 Correct 9 ms 6172 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 10 ms 5944 KB Output is correct
6 Correct 13 ms 5888 KB Output is correct
7 Correct 12 ms 6084 KB Output is correct
8 Correct 10 ms 6208 KB Output is correct
9 Correct 9 ms 6148 KB Output is correct
10 Correct 11 ms 6660 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 21464 KB Output is correct - 120000 bits used
2 Correct 222 ms 21888 KB Output is correct - 122000 bits used
3 Correct 218 ms 22448 KB Output is correct - 125000 bits used
4 Correct 242 ms 22588 KB Output is correct - 125000 bits used
5 Correct 213 ms 22408 KB Output is correct - 125000 bits used
6 Correct 241 ms 22392 KB Output is correct - 125000 bits used
7 Correct 218 ms 22632 KB Output is correct - 124828 bits used
8 Correct 219 ms 22404 KB Output is correct - 124910 bits used
9 Correct 236 ms 22500 KB Output is correct - 125000 bits used
10 Correct 212 ms 22120 KB Output is correct - 125000 bits used