Submission #293172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
293172	2020-09-07T17:24:22 Z	b00n0rp	Last supper (IOI12_supper)	C++17	100 / 100	197 ms	22768 KB

advisor

#include<bits/stdc++.h>
using namespace std;
#include "advisor.h"

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()

const int MAXN = 200005;

int ans[MAXN],last[MAXN];

vi gg[MAXN];

void ComputeAdvice(int *C, int N, int K, int M) {

	priority_queue<pii> pq;

	REP(i,K) gg[i].pb(i);
	REP(i,N){
		last[i] = -1;
		gg[C[i]].pb(i+K);
	}
	REP(i,N) gg[i].pb(N+K);
	REP(i,K){
		pq.push({*upper_bound(all(gg[i]),i),i});
		last[i] = i;
	}
	REP(i,N){
		if(last[C[i]] != -1) ans[last[C[i]]] = 1;
		else{
			int x = pq.top().S;
			pq.pop();
			last[x] = -1;
		}
		last[C[i]] = i+K;
		pq.push({*upper_bound(all(gg[C[i]]),i+K),C[i]});
	}

	REP(i,N+K) WriteAdvice(ans[i]);

}

assistant

#include<bits/stdc++.h>
using namespace std;
#include "assistant.h"

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()

const int MAXN = 200005;

void Assist(unsigned char *A, int N, int K, int R) {

	set<int> x,y;
	REP(i,K){
		if(A[i]) x.insert(i);
		else y.insert(i);
	}
	REP(i,N){
		int c = GetRequest();
		if(x.find(c) == x.end()){
			int tbr = *y.begin();
			PutBack(tbr);
			y.erase(tbr);
		}
		else{
			x.erase(c);
		}
		if(A[i+K]) x.insert(c);
		else y.insert(c);
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	9984 KB	Output is correct
2	Correct	4 ms	9984 KB	Output is correct
3	Correct	5 ms	10240 KB	Output is correct
4	Correct	7 ms	10496 KB	Output is correct
5	Correct	8 ms	10496 KB	Output is correct
6	Correct	9 ms	10752 KB	Output is correct
7	Correct	9 ms	11008 KB	Output is correct
8	Correct	9 ms	10752 KB	Output is correct
9	Correct	9 ms	10752 KB	Output is correct
10	Correct	11 ms	10752 KB	Output is correct
11	Correct	11 ms	10752 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	11520 KB	Output is correct
2	Correct	69 ms	16360 KB	Output is correct
3	Correct	180 ms	21736 KB	Output is correct
4	Correct	120 ms	21744 KB	Output is correct
5	Correct	131 ms	21832 KB	Output is correct
6	Correct	162 ms	22472 KB	Output is correct
7	Correct	181 ms	22496 KB	Output is correct
8	Correct	132 ms	19952 KB	Output is correct
9	Correct	103 ms	22768 KB	Output is correct
10	Correct	192 ms	22424 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	20016 KB	Output is correct
2	Correct	173 ms	22496 KB	Output is correct
3	Correct	175 ms	22296 KB	Output is correct
4	Correct	197 ms	22384 KB	Output is correct
5	Correct	167 ms	22392 KB	Output is correct
6	Correct	177 ms	22296 KB	Output is correct
7	Correct	172 ms	22248 KB	Output is correct
8	Correct	156 ms	21464 KB	Output is correct
9	Correct	163 ms	22720 KB	Output is correct
10	Correct	167 ms	22296 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10752 KB	Output is correct
2	Correct	10 ms	10752 KB	Output is correct
3	Correct	8 ms	10752 KB	Output is correct
4	Correct	8 ms	10496 KB	Output is correct
5	Correct	9 ms	10752 KB	Output is correct
6	Correct	10 ms	10752 KB	Output is correct
7	Correct	10 ms	10752 KB	Output is correct
8	Correct	11 ms	10816 KB	Output is correct
9	Correct	11 ms	10752 KB	Output is correct
10	Correct	13 ms	11008 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	22240 KB	Output is correct - 120000 bits used
2	Correct	181 ms	22496 KB	Output is correct - 122000 bits used
3	Correct	175 ms	22288 KB	Output is correct - 125000 bits used
4	Correct	174 ms	22288 KB	Output is correct - 125000 bits used
5	Correct	173 ms	22288 KB	Output is correct - 125000 bits used
6	Correct	174 ms	22296 KB	Output is correct - 125000 bits used
7	Correct	170 ms	22296 KB	Output is correct - 124828 bits used
8	Correct	180 ms	22416 KB	Output is correct - 124910 bits used
9	Correct	175 ms	22296 KB	Output is correct - 125000 bits used
10	Correct	166 ms	21456 KB	Output is correct - 125000 bits used