Submission #363057

#	Time	Username	Problem	Language	Result	Execution time	Memory
363057		2qbingxuan	Last supper (IOI12_supper)	C++14	100 / 100	149 ms	12092 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100025;
 
vector<int> last[maxn];
int scaffold[maxn];
int onScaffold[maxn];
int tt[maxn];

void ComputeAdvice(int *C, int N, int K, int M) {
    for (int i = 0; i < K; i++)
        scaffold[i] = i, onScaffold[i] = i;
    for (int i = K; i < N; i++)
        onScaffold[i] = -1;
    for (int i = 0; i < N; i++)
        last[i].push_back(maxn);
    for (int i = N-1; i >= 0; i--)
        last[C[i]].push_back(i);

    set<pair<int,int>> st;
    for (int i = 0; i < K; i++)
        st.insert({ -last[i].back(), i }), tt[i] = i;

    vector<bool> garbage(N + K);
    for (int i = 0; i < N; i++) {
        int req = C[i];

        if (onScaffold[req] == -1) {
            last[C[i]].pop_back();
            int pos = st.begin() -> second;
            garbage[tt[pos]] = true;
            st.erase(st.begin());
            onScaffold[req] = pos;
            onScaffold[scaffold[pos]] = -1;
            scaffold[pos] = req;
            tt[pos] = i + K;
            st.insert({ -last[C[i]].back(), pos });
        } else {
            int pos = onScaffold[C[i]];
            st.erase({ -last[C[i]].back(), pos });
            last[C[i]].pop_back();
            tt[pos] = i + K;
            st.insert({ -last[C[i]].back(), pos });
        }
    }

    for (int i = 0; i < N+K; i++)
        WriteAdvice(garbage[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 100025;
 
int scaffold[maxn];
int onScaffold[maxn];
 
void Assist(unsigned char *A, int N, int K, int R) {
    std::queue<int> q;
    for (int i = 0; i < K; i++) {
        onScaffold[i] = i;
        scaffold[i] = i;
        if (A[i])
            q.push(i);
    }

    for (int i = K; i < N; i++)
        onScaffold[i] = -1;

    for (int i = 0; i < N; i++) {
        int r = GetRequest();
        if (onScaffold[r] == -1) {
            int pos = q.front(); q.pop();
            onScaffold[scaffold[pos]] = -1;
            onScaffold[r] = pos;
            PutBack(scaffold[pos]);
            scaffold[pos] = r;
        }
        if (A[i+K])
            q.push(onScaffold[r]);
    }
}

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