Submission #274617

#	Time	Username	Problem	Language	Result	Execution time	Memory
274617		shayan_p	Last supper (IOI12_supper)	C++14	100 / 100	190 ms	13016 KiB

advisor

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#include "advisor.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int aft[maxn], lst[maxn];
bool ans[maxn];

void ComputeAdvice(int *a, int n, int k, int m){
    fill(lst, lst + n, n);
    for(int i = n-1; i >= 0; i--){
	aft[i] = lst[a[i]];
	lst[a[i]] = i;
    }
    map<int, int> mp; // color // position
    set<pii> st;// last // color
    for(int i = 0; i < k; i++){
	mp[i] = i;
	st.insert({lst[i], i});
    }
    for(int i = 0; i < n; i++){	
	if(mp.count(a[i])){
	    int c = mp[a[i]];
	    ans[c] = 1;
	    st.erase({i, a[i]});
	}
	else{
	    int c = st.rbegin()->S;
	    ans[mp[c]] = 0;
	    mp.erase(c);
	    st.erase(--st.end());
	}
	mp[a[i]] = i + k;
	st.insert({aft[i], a[i]});
    }
    for(pii p : mp){
	ans[p.S] = 0;
    }
    for(int i = 0; i < n+k; i++){
	WriteAdvice(ans[i]);
    }
}

assistant

// And you curse yourself for things you never done

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

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> qu;
bool use[maxn], in[maxn];

void Assist(unsigned char *a, int n, int k, int m){
    for(int i = 0; i < n; i++){
	use[i] = a[i+k] == 1;
	in[i] = 0;
    }    
    qu.clear();
    for(int i = 0; i < k; i++){
	in[i] = 1;
	if(a[i] == 0)
	    qu.PB(i);
    }
    for(int i = 0; i < n; i++){
	int c = GetRequest();
	if(!in[c]){
	    int cc = qu.back();
	    qu.pop_back();
	    PutBack(cc);
	    in[cc] = 0;
	    in[c] = 1;
	}	    
	if(!use[i]){
	    qu.PB(c);
	}
    }
}

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