Submission #1278480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278480		Aviansh	Last supper (IOI12_supper)	C++20	100 / 100	139 ms	10376 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

void ComputeAdvice(int *c, int n, int k, int m) {
    vector<int>occ[n];
    for(int i = 0;i<n;i++){
        occ[i].push_back(-1);
    }
    for(int i = 0;i<n;i++){
        occ[c[i]].push_back(i);
    }
    for(int i = 0;i<n;i++){
        occ[i].push_back(1e9);
    }
    int rem[n];
    fill(rem,rem+n,-1);
    set<array<int,2>>pq;
    for(int i = 0;i<k;i++){
        pq.insert({occ[i][1],i});
    }
    bool curr[n];
    fill(curr,curr+n,0);
    fill(curr,curr+k,1);
    for(int i = 0;i<n;i++){
        array<int,2>a=*(--pq.end());
        if(curr[c[i]]){
            pq.erase({i,c[i]});
            int nx = *upper_bound(occ[c[i]].begin(),occ[c[i]].end(),i);
            pq.insert({nx,c[i]});
            continue;
        }
        rem[i]=a[1];
        pq.erase(--pq.end());
        int nx = *upper_bound(occ[c[i]].begin(),occ[c[i]].end(),i);
        curr[rem[i]]=0;
        curr[c[i]]=1;
        pq.insert({nx,c[i]});
    }
    int adv1[k];
    int adv2[n];
    fill(adv1,adv1+k,0);
    fill(adv2,adv2+n,0);
    for(int i = 0;i<n;i++){
        if(rem[i]==-1)
            continue;
        int ind = *(upper_bound(occ[rem[i]].begin(),occ[rem[i]].end(),i)-1);
        if(ind==-1){
            adv1[rem[i]]=1;
        }
        else{
            adv2[ind]=1;
        }
    }
    for(int i = 0;i<k;i++){
        WriteAdvice(adv1[i]);
    }
    for(int i = 0;i<n;i++){
        WriteAdvice(adv2[i]);
    }
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {
    set<int>remable;
    set<int>curr;
    for(int i = 0;i<k;i++){
        if(a[i]==1){
            remable.insert(i);
        }
        curr.insert(i);
    }
    for(int i = 0;i<n;i++){
        int col = GetRequest();
        if(curr.find(col)==curr.end()){
            //not found
            PutBack(*remable.begin());
            curr.erase(*remable.begin());
            remable.erase(remable.begin());
        }
        if(a[i+k]==1){
            remable.insert(col);
        }
        curr.insert(col);
    }
}

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