Submission #419170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
419170	2021-06-06T14:00:18 Z	arayi	Last supper (IOI12_supper)	C++17	100 / 100	139 ms	33548 KB

advisor

#include "advisor.h"
#include <iostream>
#include <vector>
#include <queue>
#define MP make_pair
#define fr first
#define sc second
#define ad push_back
using namespace std;
const int N = 1e6 + 30;


int i1 = 0;
int col[N], b[N], c[N];
int ans[N];
vector<int> fp[N];
void ComputeAdvice(int *C, int N, int K, int M)
{
	for (int i = 0; i < N; i++) fp[i].ad(N);
	for (int i = N - 1; i >= 0; i--) fp[C[i]].ad(i);
	priority_queue <pair<int, int> > q;
	for (int i = 1; i <= K; i++) q.push(MP(fp[i - 1].back(), i)), col[i - 1] = i, b[i] = i - 1, c[i] = i - 1;
	i1 = K;
	for (int i = 0; i < N; i++)
	{
		fp[C[i]].pop_back();
		if (col[C[i]])
		{
			q.push(MP(fp[C[i]].back(), col[C[i]]));
			c[col[C[i]]] = i1 + i;
			continue;
		}
		int p = q.top().sc;
		q.pop();
		col[b[p]] = 0, col[C[i]] = p;
		ans[c[p]] = 1, c[p] = i1 + i;
		b[p] = C[i];
		q.push(MP(fp[C[i]].back(), col[C[i]]));
	}
	i1 += N;
	for (int i = 0; i < i1; i++) WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
#define MP make_pair
#define fr first
#define sc second
#define ad push
using namespace std;
const int N1 = 1e6 + 30;

int ii;
int col1[N1], b1[N1];
queue <int> fp1;
void Assist(unsigned char *A, int N, int K, int R) 
{
	for (int i = 1; i <= K; i++)
	{
		col1[i - 1] = i, b1[i] = i - 1;
		if (A[i - 1]) fp1.ad(i);
	}
	ii = K;
	for (int i = 0; i < N; i++)
	{
		int a = GetRequest();
		if (col1[a])
		{
			if (A[ii + i]) fp1.ad(col1[a]);
			continue;
		}
		int p = fp1.front();
		fp1.pop();
		PutBack(b1[p]);
		col1[b1[p]] = 0, col1[a] = p;
		b1[p] = a;
		if (A[ii + i]) fp1.ad(col1[a]);
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	24100 KB	Output is correct
2	Correct	13 ms	24164 KB	Output is correct
3	Correct	15 ms	24168 KB	Output is correct
4	Correct	16 ms	24488 KB	Output is correct
5	Correct	17 ms	24576 KB	Output is correct
6	Correct	17 ms	24612 KB	Output is correct
7	Correct	18 ms	24684 KB	Output is correct
8	Correct	18 ms	24560 KB	Output is correct
9	Correct	19 ms	24564 KB	Output is correct
10	Correct	19 ms	24712 KB	Output is correct
11	Correct	20 ms	24672 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	24848 KB	Output is correct
2	Correct	55 ms	28704 KB	Output is correct
3	Correct	132 ms	33012 KB	Output is correct
4	Correct	106 ms	32324 KB	Output is correct
5	Correct	139 ms	32328 KB	Output is correct
6	Correct	111 ms	32492 KB	Output is correct
7	Correct	110 ms	32944 KB	Output is correct
8	Correct	105 ms	31536 KB	Output is correct
9	Correct	91 ms	32904 KB	Output is correct
10	Correct	115 ms	32996 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	30208 KB	Output is correct
2	Correct	113 ms	32936 KB	Output is correct
3	Correct	110 ms	33180 KB	Output is correct
4	Correct	108 ms	32888 KB	Output is correct
5	Correct	102 ms	33112 KB	Output is correct
6	Correct	110 ms	32912 KB	Output is correct
7	Correct	108 ms	32900 KB	Output is correct
8	Correct	123 ms	32752 KB	Output is correct
9	Correct	106 ms	33548 KB	Output is correct
10	Correct	120 ms	33024 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	24564 KB	Output is correct
2	Correct	18 ms	24648 KB	Output is correct
3	Correct	17 ms	24584 KB	Output is correct
4	Correct	18 ms	24520 KB	Output is correct
5	Correct	20 ms	24560 KB	Output is correct
6	Correct	19 ms	24496 KB	Output is correct
7	Correct	18 ms	24668 KB	Output is correct
8	Correct	19 ms	24556 KB	Output is correct
9	Correct	18 ms	24648 KB	Output is correct
10	Correct	19 ms	24668 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	31748 KB	Output is correct - 120000 bits used
2	Correct	113 ms	31692 KB	Output is correct - 122000 bits used
3	Correct	112 ms	31684 KB	Output is correct - 125000 bits used
4	Correct	112 ms	31744 KB	Output is correct - 125000 bits used
5	Correct	111 ms	31748 KB	Output is correct - 125000 bits used
6	Correct	110 ms	31748 KB	Output is correct - 125000 bits used
7	Correct	122 ms	31756 KB	Output is correct - 124828 bits used
8	Correct	108 ms	31728 KB	Output is correct - 124910 bits used
9	Correct	108 ms	31796 KB	Output is correct - 125000 bits used
10	Correct	114 ms	31588 KB	Output is correct - 125000 bits used