Submission #551354

#	Time	Username	Problem	Language	Result	Execution time	Memory
551354		elazarkoren	Last supper (IOI12_supper)	C++17	0 / 100	175 ms	12560 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 1e5 + 5;

vi ind[MAX_N];

void ComputeAdvice(int *c, int n, int k, int m) {
    vb bits(k + n, 1);
    vi last(n);
    set<pii, greater<pii>> s;
    for (int i = 0; i < k; i++) {
        last[i] = i;
        ind[i].push_back(i);
    }
    for (int i = 0; i < n; i++) ind[c[i]].push_back(i + k);
    for (int i = 0; i < n; i++) ind[i].push_back(n + 1);
    for (int i = 0; i < k; i++) {
        s.insert({ind[i][1], i});
    }
    for (int i = k; i < n + k; i++) {
        int x = c[i - k];
        if (s.count({i, x})) {
            s.erase(s.find({i, x}));
        } else {
            auto [j, y] = *s.begin();
            s.erase({j, y});
            auto it = lower_bound(all(ind[y]), j);
            it--;
            bits[*it] = 0;
        }
        auto it = upper_bound(all(ind[x]), i);
        s.insert({*it, x});
    }
    for (int i = 0; i < n + k; i++) {
        WriteAdvice(bits[i]);
    }
}
//4 2 65000
//2 0 3 0

assistant

#include "assistant.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

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

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