Submission #1326637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326637		adiyer	Last supper (IOI12_supper)	C++20	26 / 100	161 ms	12884 KiB

advisor

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

using namespace std;

void ComputeAdvice(int *C, int N, int K, int M) {
    vector < int > g[N];
    set < pair < int, int > > st;
    int id = 0, a[N] = {}, c[N] = {}, val[N] = {}, pos[N] = {};
    for(int i = 0; i < N; i++) a[i] = C[i];
    for(int i = 0; i < N; i++) g[a[i]].push_back(i);
    for(int i = 0; i < N; i++) g[i].push_back(N), reverse(g[i].begin(), g[i].end());
    for(int i = 0; i < K; i++) c[i] = 1, pos[i] = i, val[i] = i, st.insert({g[i].back(), i});
    for(int i = 0; i < N; i++){
        if(i){
            if(c[a[i - 1]]) st.erase({g[a[i - 1]].back(), pos[a[i - 1]]});
            g[a[i - 1]].pop_back();
            if(c[a[i - 1]]) st.insert({g[a[i - 1]].back(), pos[a[i - 1]]});
        }
        if(c[a[i]]) continue;
        int x = ((--st.end()) -> second);

        for(int bit = 14; bit >= 0; bit--) WriteAdvice((x >> bit & 1));

        st.erase({g[val[x]].back(), x});
        c[val[x]] = pos[val[x]] = 0;
        
        val[x] = a[i];
        
        c[val[x]] = 1, pos[val[x]] = x;
        st.insert({g[val[x]].back(), x});
    }   
}

assistant

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

using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
    int a[N] = {}, c[N] = {}, id = 0;
    
    for(int i = 0; i < K; i++) a[i] = i, c[i] = 1;

    for(int i = 0; i < N; i++){
        int x = GetRequest(), k = 0;
        
        if(c[x]) continue;

        for(int bit = 14; bit >= 0; bit--) k |= (A[id++] << bit);

        PutBack(a[k]);
        
        c[a[k]] = 0, a[k] = x, c[a[k]] = 1;
    }   
}

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