Submission #171254

#	Time	Username	Problem	Language	Result	Execution time	Memory
171254		dndhk	Last supper (IOI12_supper)	C++14	100 / 100	197 ms	25320 KiB

advisor

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MAX_N = 200000;

vector<int> need[MAX_N+1];

bool chk[MAX_N+1];
priority_queue<pii> pq;
int t = 0;
int send[MAX_N*2+1];
int idx[MAX_N*2+1];

void ComputeAdvice(int *C, int N, int K, int M) {
	for(int i=0; i<N; i++)	need[i].pb(N);

	for(int i=N-1; i>=0; i--){
		need[C[i]].pb(i);
	}
	for(int i=0; i<K; i++){
		idx[i] = i;
		pq.push(make_pair(need[i].back(), i));
		chk[i] = true;
	}
	for(int i=0; i<N; i++){
		int now = C[i];
		if(chk[now]){
			send[idx[now]] = true;
			idx[now] = i+K;
		}else{
			pii p;
			while(1){
				p = pq.top(); pq.pop();
				if(need[p.second].empty() || need[p.second].back()!=p.first){
					continue;
				}
				break;
			}
			chk[p.second] = false;
		}
		need[now].pop_back();
		pq.push(make_pair(need[now].back(), now));
		idx[now] = i+K;
		chk[now] = true;
	}
	while(!pq.empty()){
		pii p = pq.top(); pq.pop();
		if(need[p.second].empty() || need[p.second].back()!=p.first){
			continue;
		}
		send[idx[p.second]] = true;
	}
	for(int i=0; i<N+K; i++){
		WriteAdvice(send[i]);
	}
}

assistant

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MAX_N1 = 200000;

bool chk2[MAX_N1+1];

vector<int> vt;

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i=0; i<K; i++){
		if(!A[i]){
			vt.pb(i);
		}else{
			chk2[i] = true;
		}
	}
	int idx = 0;
	for(int i=0; i<N; i++){
		int req = GetRequest();
		if(chk2[req]){
			chk2[req] = false;
		}else{
			PutBack(vt.back());
			vt.pop_back();
		}
		if(A[K+i]){
			chk2[req] = true;
		}else{
			vt.pb(req);
		}
	}
}

Compilation message (stderr)

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:37:6: warning: unused variable 'idx' [-Wunused-variable]
  int idx = 0;
      ^~~

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