Submission #1015618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015618	2024-07-06T15:25:22 Z	parsadox2	Last supper (IOI12_supper)	C++17	100 / 100	95 ms	14532 KB

advisor

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

#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;

int n , m , k , ar[N] , las[N];
vector <int> pos[N];
bool B[N << 1];

void ComputeAdvice(int *C, int nn, int kk, int mm){
	n = nn;
	m = mm;
	k = kk;
	for(int i = 0 ; i < n ; i++)
	{
		ar[i] = C[i];
		pos[i].push_back(n + 1);
	}
	for(int i = n - 1 ; i >= 0 ; i--)
		pos[ar[i]].push_back(i);
	set <pair <int , int>> st;
	for(int i = 0 ; i < k ; i++)
	{
		las[i] = i;
		st.insert(make_pair(pos[i].back() , i));
	}
	for(int i = 0 ; i < n ; i++)
	{
		int x = ar[i];
		auto it = st.find(make_pair(i , x));
		if(it != st.end())
		{
			st.erase(it);
			pos[x].pop_back();
			las[x] = i + k;
			st.insert(make_pair(pos[x].back() , x));
		}
		else
		{
			auto rem = st.end();  rem--;
			auto now = *rem;
			B[las[now.S]] = 1;
			//cout << now.S << " " << x << endl;
			st.erase(rem);
			pos[x].pop_back();
			las[x] = i + k;
			st.insert(make_pair(pos[x].back() , x));
		}
	}
	for(int i = 0 ; i < n + k ; i++)
	{
		//cout << B[i];
		WriteAdvice(B[i]);
	}
	//cout << endl;
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"
 
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;

int n2 , k2 , r2;

void Assist(unsigned char *ar, int nn, int kk, int rr) {
	n2 = nn;
	k2 = kk;
	r2 = rr;
	set <int> st;
	for(int i = 0 ; i < k2 ; i++)
		st.insert(i);
	vector <int> vec;
	for(int i = 0 ; i < k2 ; i++)  if(ar[i])
		vec.push_back(i);
	for(int i = k2 ; i < k2 + n2 ; i++)
	{
		int now = GetRequest();
		if(st.find(now) == st.end())
		{
			PutBack(vec.back());
			st.erase(vec.back());
			st.insert(now);
			vec.pop_back();
		}
		if(ar[i])
			vec.push_back(now);
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3100 KB	Output is correct
2	Correct	1 ms	3100 KB	Output is correct
3	Correct	1 ms	3348 KB	Output is correct
4	Correct	2 ms	3380 KB	Output is correct
5	Correct	3 ms	3412 KB	Output is correct
6	Correct	3 ms	3608 KB	Output is correct
7	Correct	3 ms	3412 KB	Output is correct
8	Correct	3 ms	3412 KB	Output is correct
9	Correct	4 ms	3412 KB	Output is correct
10	Correct	4 ms	3672 KB	Output is correct
11	Correct	4 ms	3404 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3988 KB	Output is correct
2	Correct	37 ms	7708 KB	Output is correct
3	Correct	90 ms	14532 KB	Output is correct
4	Correct	48 ms	10872 KB	Output is correct
5	Correct	70 ms	10964 KB	Output is correct
6	Correct	69 ms	11360 KB	Output is correct
7	Correct	80 ms	12872 KB	Output is correct
8	Correct	62 ms	11888 KB	Output is correct
9	Correct	43 ms	11604 KB	Output is correct
10	Correct	86 ms	13936 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	11648 KB	Output is correct
2	Correct	83 ms	13524 KB	Output is correct
3	Correct	95 ms	13368 KB	Output is correct
4	Correct	84 ms	13628 KB	Output is correct
5	Correct	74 ms	13300 KB	Output is correct
6	Correct	84 ms	13376 KB	Output is correct
7	Correct	85 ms	13376 KB	Output is correct
8	Correct	76 ms	13472 KB	Output is correct
9	Correct	67 ms	14488 KB	Output is correct
10	Correct	83 ms	13380 KB	Output is correct

Subtask #4

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3396 KB	Output is correct
2	Correct	3 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	3 ms	3412 KB	Output is correct
5	Correct	3 ms	3404 KB	Output is correct
6	Correct	3 ms	3408 KB	Output is correct
7	Correct	4 ms	3404 KB	Output is correct
8	Correct	4 ms	3412 KB	Output is correct
9	Correct	4 ms	3404 KB	Output is correct
10	Correct	5 ms	3936 KB	Output is correct

Subtask #5

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	12912 KB	Output is correct - 120000 bits used
2	Correct	81 ms	13456 KB	Output is correct - 122000 bits used
3	Correct	81 ms	13524 KB	Output is correct - 125000 bits used
4	Correct	88 ms	13404 KB	Output is correct - 125000 bits used
5	Correct	84 ms	13472 KB	Output is correct - 125000 bits used
6	Correct	87 ms	13372 KB	Output is correct - 125000 bits used
7	Correct	88 ms	13672 KB	Output is correct - 124828 bits used
8	Correct	82 ms	13572 KB	Output is correct - 124910 bits used
9	Correct	82 ms	13684 KB	Output is correct - 125000 bits used
10	Correct	79 ms	13488 KB	Output is correct - 125000 bits used