Submission #986917

#	Time	Username	Problem	Language	Result	Execution time	Memory
986917		Sharky	Last supper (IOI12_supper)	C++17	0 / 100	178 ms	83320 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> req(N + K, 0);
    for (int i = 0; i < K; i++) req[i] = i;
    for (int i = K; i < N + K; i++) req[i] = C[i - K];
    vector<int> s(N + K, 0);
    vector<vector<int>> add(N), del(N);
    vector<queue<int>> pos(N);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < N + K; i++) {
        pos[req[i]].push(i);
        if (i < K) scaff[i] = true;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 0; i < N + K; i++) {
        if (!scaff[req[i]]) {
            auto [dist, col] = pq.top();
            pq.pop();
            del[col].push_back(i);
            scaff[col] = false;
            scaff[req[i]] = true;
        }
        pos[req[i]].pop();
        int tp = inf;
        if (!pos[req[i]].empty()) tp = pos[req[i]].front();
        pq.push({tp, req[i]});
        add[req[i]].push_back(i);
    }
    for (int i = 0; i < N; i++) del[i].push_back(N + K);
    for (int i = 0; i < N + K; i++) {
        auto it = upper_bound(add[req[i]].begin(), add[req[i]].end(), i);
        int k = *upper_bound(del[req[i]].begin(), del[req[i]].end(), i);
        if (it == add[req[i]].end() || (*it) > k) s[i] = 1;
        WriteAdvice(s[i]);
    }
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
    assert(R == N + K);
    vector<set<int>> st(2);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < K; i++) {
        st[A[i]].insert(i);
        scaff[i] = true;
    }
    for (int i = K; i < N + K; i++) {
        int req = GetRequest();
        if (!st[1].empty() && !scaff[req]) {
            int f = *st[1].begin();
            st[1].erase(f);
            PutBack(f);
            scaff[f] = false;
            scaff[req] = true;
        }
        st[0].erase(req);
        st[A[i]].insert(req);
    }
}

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