Submission #888788

#	Time	Username	Problem	Language	Result	Execution time	Memory
888788		abcvuitunggio	Last supper (IOI12_supper)	C++17	100 / 100	94 ms	13968 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> pos[100001];
int a[200001],b[100001],c[100001];
set <pair <int, int>> s;
void ComputeAdvice(int *C, int N, int K, int M){
    for (int i=0;i<N;i++)
        pos[i].push_back(1000000);
    for (int i=N-1;i>=0;i--)
        pos[C[i]].push_back(i+K);
    for (int i=0;i<K;i++){
        b[i]=i;
        c[i]=1;
        pos[i].push_back(i);
        pos[i].pop_back();
        s.insert({pos[i].back(),i});
    }
    for (int i=0;i<N;i++){
        if (c[C[i]]){
            a[b[C[i]]]=1;
            b[C[i]]=i+K;
            s.erase({pos[C[i]].back(),C[i]});
        }
        else{
            b[C[i]]=i+K;
            auto [x,y]=*--s.end();
            s.erase(--s.end());
            c[C[i]]=1;
            c[y]=0;
        }
        pos[C[i]].pop_back();
        s.insert({pos[C[i]].back(),C[i]});
    }
    for (int i=0;i<N+K;i++)
        WriteAdvice(a[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
int ch[100001];
void Assist(unsigned char *A, int N, int K, int R){
    vector <int> ve;
    for (int i=0;i<K;i++){
        if (!A[i])
            ve.push_back(i);
        ch[i]=1;
    }
    for (int i=0;i<N;i++){
        int c=GetRequest();
        if (!ch[c]){
            PutBack(ve.back());
            ch[ve.back()]=0;
            ch[c]=1;
            ve.pop_back();
        }
        if (!A[i+K])
            ve.push_back(c);
    }
}

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