Submission #990484

#	Time	Username	Problem	Language	Result	Execution time	Memory
990484		12345678	Last supper (IOI12_supper)	C++17	0 / 100	22 ms	9232 KiB

advisor

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

using namespace std;

const int nxx=1e5+5;

int bits;
vector<int> d[nxx], idx(nxx);
set<pair<int, int>> mx;

void ComputeAdvice(int *C, int N, int K, int M) {
    bits=ceil(log2(K));
    for (int i=N-1; i>=0; i--) d[C[i]].push_back(i);
    for (int i=0; i<K; i++)
    {
        idx[i]=i;
        if (d[i].empty()) mx.insert({1e9, i});
        else mx.insert({d[i].back(), i});
    }
    for (int i=0; i<N; i++)
    {
        if (mx.find({i, C[i]})!=mx.end())
        {
            d[C[i]].pop_back();
            mx.erase({i, C[i]});
        }
        else
        {
            auto col=prev(mx.end())->second;
            mx.erase(prev(mx.end()));
            d[C[i]].pop_back();
            idx[C[i]]=idx[col];
            for (int j=0; j<bits; j++) WriteAdvice(idx[C[i]]&(1<<j)); 
            //cout<<"remove "<<C[i]<<' '<<idx[C[i]]<<'\n';
        }
        if (d[C[i]].empty()) mx.insert({1e9, C[i]});
        else mx.insert({d[C[i]].back(), C[i]});
    }
}

assistant

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

using namespace std;

const int nx=1e5+5;

int c[nx], bit, t;
set<int> s;

void Assist(unsigned char *A, int N, int K, int R) {
    bit=ceil(log2(K));
    for (int i=0; i<K; i++) c[i]=i, s.insert(i);
    for (int i=0; i<N; i++)
    {
        auto cur=GetRequest();
        if (s.find(cur)!=s.end()) continue;
        int tmp=0;
        for (int j=0; j<bit; j++) if (A[t++]==1) tmp+=(1<<j);
        s.erase(c[tmp]);
        PutBack(c[tmp]);
        s.insert(cur);
        c[tmp]=cur;
    }
}

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