Submission #571866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571866	2022-06-02T23:48:01 Z	sofapuden	Last supper (IOI12_supper)	C++14	100 / 100	231 ms	14324 KB

advisor

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

using namespace std;

void ComputeAdvice(int *c, int n, int k, int m) {
	vector<int> ord;
	vector<int> nxt(n+k);
	vector<int> prv(n+k);
	map<int,int> M;
	for(int i = 0; i < k; ++i)ord.push_back(i);
	for(int i = 0; i < n; ++i)ord.push_back(c[i]);
	for(int i = 0; i < n+k; ++i){
		if(M.find(ord[i]) == M.end())prv[i] = -1;
		else prv[i] = M[ord[i]];
		M[ord[i]] = i;
	}
	M.clear();
	for(int i = n+k-1; ~i; --i){
		if(!M[ord[i]])nxt[i] = n+k;
		else nxt[i] = M[ord[i]];
		M[ord[i]] = i;
	}
	vector<int> rem(n+k,0);
	multiset<int> pq;
	for(int i = 0; i < k; ++i){
		pq.insert(nxt[i]);
	}
	for(int i = k; i < n+k; ++i){
		if(pq.count(i)){
			pq.insert(nxt[i]);
			pq.erase(i);
			rem[prv[i]] = 1;
			continue;
		}
		pq.erase(prev(pq.end()));
		pq.insert(nxt[i]);
	}
	for(auto x : rem){
		WriteAdvice(x);
	}
}

assistant

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

using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {
	set<int> on;
	vector<int> ord;
	for(int i = 0; i < k; ++i){
		on.insert(i);
		ord.push_back(i);
	}
	int cn = 0;
	int cn2 = 0;
	for(int i = 0; i < n; ++i){
    	int req = GetRequest();
		ord.push_back(req);
		if(on.count(req))continue;
		while(a[cn2++] == 1)cn++;
		on.insert(req);
		on.erase(ord[cn]);
		PutBack(ord[cn++]);
	}
}

/* 
 * Query types:
 * GetRequest()
 * PutBack(int x)
 *
 */

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	512 KB	Output is correct
2	Correct	1 ms	520 KB	Output is correct
3	Correct	3 ms	860 KB	Output is correct
4	Correct	3 ms	796 KB	Output is correct
5	Correct	5 ms	1056 KB	Output is correct
6	Correct	8 ms	1084 KB	Output is correct
7	Correct	6 ms	932 KB	Output is correct
8	Correct	7 ms	1216 KB	Output is correct
9	Correct	7 ms	1080 KB	Output is correct
10	Correct	10 ms	1296 KB	Output is correct
11	Correct	8 ms	1072 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	1668 KB	Output is correct
2	Correct	82 ms	4432 KB	Output is correct
3	Correct	216 ms	14324 KB	Output is correct
4	Correct	136 ms	8736 KB	Output is correct
5	Correct	165 ms	8820 KB	Output is correct
6	Correct	165 ms	9488 KB	Output is correct
7	Correct	188 ms	11092 KB	Output is correct
8	Correct	184 ms	11624 KB	Output is correct
9	Correct	98 ms	5888 KB	Output is correct
10	Correct	225 ms	12396 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	9596 KB	Output is correct
2	Correct	199 ms	11648 KB	Output is correct
3	Correct	231 ms	11772 KB	Output is correct
4	Correct	195 ms	11628 KB	Output is correct
5	Correct	198 ms	10096 KB	Output is correct
6	Correct	192 ms	11820 KB	Output is correct
7	Correct	209 ms	11856 KB	Output is correct
8	Correct	194 ms	13256 KB	Output is correct
9	Correct	174 ms	10508 KB	Output is correct
10	Correct	197 ms	11748 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1084 KB	Output is correct
2	Correct	7 ms	1204 KB	Output is correct
3	Correct	6 ms	948 KB	Output is correct
4	Correct	5 ms	1080 KB	Output is correct
5	Correct	6 ms	1084 KB	Output is correct
6	Correct	6 ms	1076 KB	Output is correct
7	Correct	9 ms	1096 KB	Output is correct
8	Correct	9 ms	1080 KB	Output is correct
9	Correct	7 ms	1208 KB	Output is correct
10	Correct	11 ms	1584 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	11212 KB	Output is correct - 120000 bits used
2	Correct	192 ms	11568 KB	Output is correct - 122000 bits used
3	Correct	200 ms	11840 KB	Output is correct - 125000 bits used
4	Correct	206 ms	11804 KB	Output is correct - 125000 bits used
5	Correct	214 ms	11748 KB	Output is correct - 125000 bits used
6	Correct	200 ms	11820 KB	Output is correct - 125000 bits used
7	Correct	220 ms	11840 KB	Output is correct - 124828 bits used
8	Correct	191 ms	11860 KB	Output is correct - 124910 bits used
9	Correct	195 ms	11896 KB	Output is correct - 125000 bits used
10	Correct	209 ms	13132 KB	Output is correct - 125000 bits used