Submission #463835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
463835	2021-08-11T21:26:44 Z	dutch	Last supper (IOI12_supper)	C++17	100 / 100	78 ms	6056 KB

advisor

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

void ComputeAdvice(int *C, int N, int K, int M){
	int next[N], last[N];
	fill(last, last+N, N);
	bool on[N], r[N+K] = {};

	for(int i=N; --i>=0; ){
		next[i] = last[C[i]];
		last[C[i]] = i;
		on[i] = i < K;
	}
	priority_queue<array<int, 2>> q;

	for(int i=0; i<N; ++i){
		if(i < K) q.push({last[i], i});
		last[i] = i < K ? i : -1;
	}

	for(int i=0; i<N; ++i){
		if(!on[C[i]]){
			while(!on[q.top()[1]]) q.pop();
			int j = q.top()[1]; q.pop();
			r[last[j]] = !(on[j] = 0);
		}
		q.push({next[i], C[i]});
		on[C[i]] = 1;
		last[C[i]] = K + i;
	}
	for(int i=0; i<N+K; ++i) WriteAdvice(r[i]);
}

assistant

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

void Assist(unsigned char *A, int N, int K, int R){
	vector<int> s;
	bool on[N] = {};
	for(int i=0; i<K; ++i){
		on[i] = 1;
		if(!!A[i]) s.push_back(i);
	}

	for(int i=0; i<N; ++i){
		int j = GetRequest();
		if(!on[j]){
			PutBack(s.back());
			on[s.back()] = 0;
			s.pop_back();
			on[j] = 1;
		}
		if(!!A[K+i]) s.push_back(j);
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	484 KB	Output is correct
2	Correct	0 ms	484 KB	Output is correct
3	Correct	2 ms	616 KB	Output is correct
4	Correct	3 ms	644 KB	Output is correct
5	Correct	3 ms	664 KB	Output is correct
6	Correct	4 ms	772 KB	Output is correct
7	Correct	3 ms	796 KB	Output is correct
8	Correct	4 ms	668 KB	Output is correct
9	Correct	5 ms	668 KB	Output is correct
10	Correct	5 ms	808 KB	Output is correct
11	Correct	5 ms	796 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1076 KB	Output is correct
2	Correct	35 ms	3056 KB	Output is correct
3	Correct	76 ms	5836 KB	Output is correct
4	Correct	65 ms	5372 KB	Output is correct
5	Correct	71 ms	5524 KB	Output is correct
6	Correct	69 ms	5532 KB	Output is correct
7	Correct	73 ms	5872 KB	Output is correct
8	Correct	62 ms	4928 KB	Output is correct
9	Correct	63 ms	5536 KB	Output is correct
10	Correct	76 ms	5856 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	3748 KB	Output is correct
2	Correct	74 ms	5772 KB	Output is correct
3	Correct	78 ms	5784 KB	Output is correct
4	Correct	75 ms	6056 KB	Output is correct
5	Correct	69 ms	5904 KB	Output is correct
6	Correct	74 ms	5756 KB	Output is correct
7	Correct	73 ms	5848 KB	Output is correct
8	Correct	75 ms	5944 KB	Output is correct
9	Correct	69 ms	5908 KB	Output is correct
10	Correct	74 ms	5856 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	5 ms	792 KB	Output is correct
3	Correct	3 ms	668 KB	Output is correct
4	Correct	3 ms	668 KB	Output is correct
5	Correct	4 ms	792 KB	Output is correct
6	Correct	5 ms	668 KB	Output is correct
7	Correct	5 ms	796 KB	Output is correct
8	Correct	5 ms	816 KB	Output is correct
9	Correct	5 ms	796 KB	Output is correct
10	Correct	5 ms	804 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	4560 KB	Output is correct - 120000 bits used
2	Correct	73 ms	4588 KB	Output is correct - 122000 bits used
3	Correct	77 ms	4652 KB	Output is correct - 125000 bits used
4	Correct	74 ms	4652 KB	Output is correct - 125000 bits used
5	Correct	75 ms	4632 KB	Output is correct - 125000 bits used
6	Correct	75 ms	4588 KB	Output is correct - 125000 bits used
7	Correct	76 ms	4664 KB	Output is correct - 124828 bits used
8	Correct	74 ms	4576 KB	Output is correct - 124910 bits used
9	Correct	76 ms	4644 KB	Output is correct - 125000 bits used
10	Correct	73 ms	4580 KB	Output is correct - 125000 bits used