Submission #114332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114332	2019-05-31T22:58:01 Z	nxteru	Last supper (IOI12_supper)	C++14	100 / 100	140 ms	8312 KB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,k,nex[200005],p[200005],ex[200005],ans[200005];
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N,k=K;
	for(int i=0;i<n;i++)p[i]=n,ex[i]=-1;
	for(int i=n-1;i>=0;i--){
		nex[i]=p[C[i]];
		p[C[i]]=i;
	}
	priority_queue<P>d;
	for(int i=0;i<k;i++)d.push(P(p[i],i)),ex[i]=i;
	for(int i=0;i<n;i++){
		int c=C[i];
		if(ex[c]!=-1)ans[ex[c]]=1;
		else{
			int y;
			while(1){
				y=d.top().second;
				d.pop();
				if(ex[y]==-1)continue;
				ex[y]=-1;
				break;
			}
		}
		ex[c]=k+i;
		d.push(P(nex[i],c));
	}
	for(int i=0;i<k+n;i++)WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
set<int>x,y;
void Assist(unsigned char *A, int N, int K, int R) {
	for(int i=0;i<K;i++){
		if(A[i]==0)x.insert(i);
		else y.insert(i);
	}
	for(int i=K;i<N+K;i++){
		int c=GetRequest();
		if(y.find(c)!=y.end())y.erase(c);
		else{
			PutBack(*x.begin());
			x.erase(x.begin());
		}
		if(A[i]==0)x.insert(c);
		else y.insert(c);
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	856 KB	Output is correct
2	Correct	4 ms	880 KB	Output is correct
3	Correct	6 ms	912 KB	Output is correct
4	Correct	6 ms	1164 KB	Output is correct
5	Correct	6 ms	1104 KB	Output is correct
6	Correct	7 ms	1024 KB	Output is correct
7	Correct	8 ms	1280 KB	Output is correct
8	Correct	8 ms	1152 KB	Output is correct
9	Correct	8 ms	1136 KB	Output is correct
10	Correct	9 ms	1280 KB	Output is correct
11	Correct	8 ms	1096 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1544 KB	Output is correct
2	Correct	47 ms	4328 KB	Output is correct
3	Correct	120 ms	7948 KB	Output is correct
4	Correct	68 ms	7664 KB	Output is correct
5	Correct	73 ms	7760 KB	Output is correct
6	Correct	94 ms	7880 KB	Output is correct
7	Correct	118 ms	8160 KB	Output is correct
8	Correct	84 ms	6516 KB	Output is correct
9	Correct	65 ms	7544 KB	Output is correct
10	Correct	125 ms	8296 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	5928 KB	Output is correct
2	Correct	122 ms	8248 KB	Output is correct
3	Correct	121 ms	8216 KB	Output is correct
4	Correct	124 ms	8176 KB	Output is correct
5	Correct	118 ms	8312 KB	Output is correct
6	Correct	125 ms	8216 KB	Output is correct
7	Correct	122 ms	8176 KB	Output is correct
8	Correct	96 ms	7376 KB	Output is correct
9	Correct	114 ms	7920 KB	Output is correct
10	Correct	140 ms	8208 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1280 KB	Output is correct
2	Correct	8 ms	1096 KB	Output is correct
3	Correct	7 ms	1024 KB	Output is correct
4	Correct	7 ms	1024 KB	Output is correct
5	Correct	7 ms	1024 KB	Output is correct
6	Correct	7 ms	1024 KB	Output is correct
7	Correct	8 ms	1280 KB	Output is correct
8	Correct	8 ms	1096 KB	Output is correct
9	Correct	8 ms	1024 KB	Output is correct
10	Correct	9 ms	1368 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	7008 KB	Output is correct - 120000 bits used
2	Correct	118 ms	7312 KB	Output is correct - 122000 bits used
3	Correct	118 ms	7080 KB	Output is correct - 125000 bits used
4	Correct	121 ms	6936 KB	Output is correct - 125000 bits used
5	Correct	124 ms	6936 KB	Output is correct - 125000 bits used
6	Correct	122 ms	7096 KB	Output is correct - 125000 bits used
7	Correct	123 ms	7032 KB	Output is correct - 124828 bits used
8	Correct	121 ms	6928 KB	Output is correct - 124910 bits used
9	Correct	125 ms	6944 KB	Output is correct - 125000 bits used
10	Correct	105 ms	6336 KB	Output is correct - 125000 bits used