oj.uz

Submission #586768

# Submission time Handle Problem Language Result Execution time Memory
586768 2022-06-30T16:51:03 Z keta_tsimakuridze Last supper (IOI12_supper) C++14
0 / 100
 208 ms 24536 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]);

        cur.insert({*s[x].upper_bound(i), i});
    }
     //   cout << "advisoris " << ans << endl;
    for(int i = 0; i < N + K; i++) WriteAdvice(f[i]);
}

#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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5260 KB Output is correct
2 Incorrect 3 ms 5260 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 7052 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 20380 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6072 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 23224 KB Output isn't correct - not an optimal way
2 Incorrect 197 ms 23840 KB Output isn't correct - not an optimal way
3 Incorrect 202 ms 24424 KB Output isn't correct - not an optimal way
4 Incorrect 193 ms 24416 KB Output isn't correct - not an optimal way
5 Incorrect 208 ms 24536 KB Output isn't correct - not an optimal way
6 Incorrect 204 ms 24332 KB Output isn't correct - not an optimal way
7 Incorrect 194 ms 24380 KB Output isn't correct - not an optimal way
8 Incorrect 202 ms 24500 KB Output isn't correct - not an optimal way
9 Incorrect 194 ms 24292 KB Output isn't correct - not an optimal way
10 Correct 177 ms 23272 KB Output is correct - 125000 bits used