Submission #1134685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134685		adaawf	Last supper (IOI12_supper)	C++20	100 / 100	90 ms	5704 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
int f[200005], l[200005], g[200005], d[200005], dd[200005], c[200005];
void ComputeAdvice(int *C, int n, int k, int m) {
    int h = n + k;
    for (int i = h - 1; i >= k; i--) {
        c[i] = C[i - k];
    }
    for (int i = 0; i < n; i++) {
        l[i] = 1e9; d[i] = dd[i] = 0;
    }
    for (int i = h - 1; i >= k; i--) {
        f[i] = l[c[i]];
        l[c[i]] = i;
    }
    set<pair<int, int>> s;
    for (int i = 0; i < k; i++) {
        c[i] = i;
        s.insert({-l[i], i});
        g[i] = i;
        dd[i] = 1;
    }
    for (int i = k; i < h; i++) {
        if (dd[c[i]] == 1) {
            s.erase({-i, g[c[i]]});
            s.insert({-f[i], i});
        }
        else {
            auto w = *s.begin();
            d[w.second] = 1;
            s.erase(s.begin());
            dd[c[w.second]] = 0;
            dd[c[i]] = 1;
            s.insert({-f[i], i});
        }
        g[c[i]] = i;
    }
    for (int i = 0; i < h; i++) WriteAdvice(d[i]);
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
int f[200005], l[200005], g[200005], d[200005], dd[200005];
void Assist(unsigned char *a, int n, int k, int r) {
    int h = n + k;
    for (int i = 0; i < n; i++) {
        dd[i] = 0;
    }
    stack<int> s;
    for (int i = 0; i < k; i++) {
        if (a[i]) s.push(i);
        dd[i] = 1;
    }
    for (int i = k; i < h; i++) {
        int x = GetRequest();
        if (dd[x] == 0) {
            PutBack(s.top());
            dd[s.top()] = 0;
            s.pop();
            dd[x] = 1;
        }
        if (a[i]) s.push(x);
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39