Submission #1158814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158814		SmuggingSpun	Last supper (IOI12_supper)	C++20	100 / 100	106 ms	7752 KiB

advisor

#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
void ComputeAdvice(int *C, int n, int k, int m){ 
    if(n <= 5000 && m == 65000){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 13; j++){
                WriteAdvice((1 << j & C[i]) ? 1 : 0);
            }
        }
        return;
    }
    vector<bool>ans(k + n, false);
    vector<int>cp(n, -1);
    vector<vector<int>>pos(n);
    for(int i = 0; i < n; i++){
        pos[C[i]].emplace_back(i);
    }
    for(int i = 0; i < n; i++){
        reverse(pos[i].begin(), pos[i].end());
    }
    set<pair<int, int>>S;
    for(int i = 0; i < k; i++){
        S.emplace(pos[i].empty() ? n : pos[i].back(), cp[i] = i);
    }    
    for(int i = 0; i < n; i++){
        pos[C[i]].pop_back();
        if(cp[C[i]] == -1){
            auto [index, value] = *S.rbegin();
            S.erase(prev(S.end()));
            cp[value] = -1;
            cp[C[i]] = i + k;
        }
        else{
            ans[cp[C[i]]] = true;
            cp[C[i]] = i + k;
            S.erase(S.begin());
        }
        S.emplace(pos[C[i]].empty() ? n : pos[C[i]].back(), C[i]);
    }
    for(int i = 0; i < n + k; i++){
        WriteAdvice((unsigned char)ans[i]);
    }
}

assistant

#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;
void Assist(unsigned char *A, int n, int k, int R){
    if(n <= 5000 && R == 13 * n){
        vector<vector<int>>p(n);
        for(int i = 0; i < n; i++){
            int num = 0;
            for(int j = 0; j < 13; j++){
                if(A[i * 13 + j] == 1){
                    num |= 1 << j;
                }
            }
            p[num].emplace_back(i);
        }
        for(int i = 0; i < n; i++){
            reverse(p[i].begin(), p[i].end());
        }
        vector<int>scaf(k);
        iota(scaf.begin(), scaf.end(), 0);
        for(int i = 0; i < n; i++){
            int color = GetRequest();
            if(find(scaf.begin(), scaf.end(), color) == scaf.end()){
                int candidate = 0;
                for(int j = 0; j < scaf.size(); j++){
                    int x = scaf[j];
                    while(!p[x].empty() && p[x].back() <= i){
                        p[x].pop_back();
                    }
                    if(p[x].empty() || (!p[scaf[candidate]].empty() && p[scaf[candidate]].back() < p[x].back())){
                        candidate = j;
                    }
                }
                PutBack(scaf[candidate]);
                swap(scaf[candidate], scaf.back());
                scaf.pop_back();
                scaf.emplace_back(color);
            }
        }
        return;
    }
    vector<int>inactive;
    set<int>scaf;
    for(int i = 0; i < k; i++){
        if(A[i] == 0){
            inactive.emplace_back(i);
        }
        scaf.insert(i);
    }
    for(int i = 0; i < n; i++){
        int x = GetRequest();
        if(scaf.find(x) == scaf.end()){
            while(scaf.find(inactive.back()) == scaf.end()){
                inactive.pop_back();
            }
            PutBack(inactive.back());
            scaf.erase(inactive.back());
            inactive.pop_back();
            scaf.insert(x);
        }
        if(A[i + k] == 0){
            inactive.emplace_back(x);
        }
    }
}

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