Submission #502240

#	Time	Username	Problem	Language	Result	Execution time	Memory
502240		blue	Last supper (IOI12_supper)	C++17	100 / 100	172 ms	8680 KiB

advisor

#include "advisor.h"
#include <deque>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

using vi = vector<int>;

void ComputeAdvice(int *C, int N, int K, int M)
{
    vi curr(N, N);
    vi nxt(N, 0);
    for(int i = N-1; i >= 0; i--)
    {
        nxt[i] = curr[C[i]];
        curr[C[i]] = i;
    }

    set<pair<int, int> > scaffold;
    for(int c = 0; c < K; c++) scaffold.insert({curr[c], c});



    vi removed(N+K, 1);

    vi prv(N, -1);
    for(int c = 0; c < K; c++) prv[c] = c;

    for(int i = 0; i < N; i++)
    {
        if(scaffold.find({curr[C[i]], C[i]}) != scaffold.end())
        {
            scaffold.erase({curr[C[i]], C[i]});

            curr[C[i]] = nxt[curr[C[i]]];
            scaffold.insert({curr[C[i]], C[i]});

            // if(prv[C])
            removed[prv[C[i]]] = 0;
        }
        else
        {
            int z = scaffold.rbegin()->second;
            scaffold.erase({curr[z], z});

            curr[C[i]] = nxt[curr[C[i]]];
            scaffold.insert({curr[C[i]], C[i]});

            // cerr << "remove\n";

        }
        prv[C[i]] = K+i;
    }

    // cerr << "advice = ";
    // for(int v = 0; v < N+K; v++) cerr << removed[v] << ' ';
    // cerr << '\n';

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

assistant

#include "assistant.h"
#include <set>
#include <iostream>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R)
{
    set<int> good, bad;
    for(int i = 0; i < K; i++)
    {
        if(A[i]) bad.insert(i);
        else good.insert(i);
    }

    for(int i = 0; i < N; i++)
    {
        int c = GetRequest();

        if(good.find(c) == good.end() && bad.find(c) == bad.end())
        {
            int r = *bad.begin();
            bad.erase(r);
            PutBack(r);
        }

        good.erase(c);
        bad.erase(c);
        if(A[i+K])
            bad.insert(c);
        else
            good.insert(c);
    }
}

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