Submission #1202968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202968		Hanksburger	Last supper (IOI12_supper)	C++20	100 / 100	89 ms	4920 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
int pos[100005], nxt[100005];
pair<int, int> ins[100005];
set<pair<int, int> > s;
void ComputeAdvice(int *c, int n, int k, int m)
{
    for (int i=0; i<n; i++)
        pos[i]=n, ins[i]={1, -1};
    for (int i=n-1; i>=0; i--)
    {
        nxt[i]=pos[c[i]];
        pos[c[i]]=i;
    }
    for (int i=0; i<k; i++)
    {
        s.insert({-pos[i], i});
        ins[i]={-pos[i], i};
    }
    vector<int> v(n+k, 0);
    for (int i=0; i<n; i++)
    {
        if (ins[c[i]].first<=0)
        {
            v[s.find(ins[c[i]])->second]=1;
            s.erase(ins[c[i]]);
        }
        else
        {
            if (s.begin()->second<k)
                ins[s.begin()->second]={1, -1};
            else
                ins[c[s.begin()->second-k]]={1, -1};
            s.erase(s.begin());
        }
        s.insert({-nxt[i], k+i});
        ins[c[i]]={-nxt[i], k+i};
    }
    for (int i=0; i<n+k; i++)
        WriteAdvice(v[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[100005];
set<pair<int, int> > t;
void Assist(unsigned char *a, int n, int k, int r)
{
    for (int i=0; i<n; i++)
        p[i]={-1, -1};
    for (int i=0; i<k; i++)
    {
        t.insert({a[i], i});
        p[i]={a[i], i};
    }
    for (int i=k; i<k+n; i++)
    {
        int c=GetRequest();
        if (p[c].first>=0)
            t.erase(p[c]);
        else
        {
            PutBack(t.begin()->second);
            p[t.begin()->second]={-1, -1};
            t.erase(t.begin());
        }
        t.insert({a[i], c});
        p[c]={a[i], c};
    }
}

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