답안 #274818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274818	2020-08-19T16:13:46 Z	amoo_safar	최후의 만찬 (IOI12_supper)	C++17	100 / 100	182 ms	10992 KB

advisor

// That's How much we have in common

#include "advisor.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

void ComputeAdvice(int *C, int n, int k, int M) {
	assert(n + k <= M);
	vector<int> A(n + k, 0);
	for(int i = 0; i < k; i++) A[i] = i;
	for(int i = 0; i < n; i++) A[i + k] = C[i];

	vector<int> LA(n, n + k), nx(n + k, 0);
	vector<int> inp(n + k + 1, 0);

	for(int i = n + k - 1; i >= 0; i--){
		nx[i] = LA[A[i]];
		inp[nx[i]] = i;
		LA[A[i]] = i;
	}
	set<pii> st;
	for(int i = 0; i < k; i++) st.insert({nx[i], A[i]});
	vector<int> ans(n + k, 0);

	for(int i = k; i < n + k; i++){
		if(st.count({i, A[i]})){
			ans[inp[i]] = 1;
			st.erase({i, A[i]});
		} else {
			st.erase(--st.end());
		}
		st.insert({nx[i], A[i]});
	}

	for(auto x : ans) WriteAdvice(x);
	//cerr << "! ";
	//for(auto x : ans) cerr << x;
	//cerr << '\n';
}
/*
4 2 65000
2 0 3 0

*/

assistant

#include "assistant.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

void Assist(unsigned char *As, int n, int k, int R) {
	assert(R == n + k);
	vector<int> A(n + k, 0);
	for(int i = 0; i < k; i++) A[i] = i;
	//for(int i = 0; i < n; i++) A[i + k] = C[i];

	set<pii> st;
	for(int i = 0; i < k; i++) st.insert({As[i], A[i]});
	//cerr << "!! ";
	int x;
	for(int i = 0; i < n + k; i++){
		x = As[i];
		//cerr << x;
	}
	//cerr << '\n';
	for(int i = k; i < n + k; i++){
		A[i] = GetRequest();

		if(st.count({1, A[i]})){
			st.erase({1, A[i]});
		} else {
			//cerr << "? " << st.begin() -> F << ' ' << st.begin() -> S << '\n';
			assert((st.begin() -> F == 0));
			PutBack(st.begin() -> S);
			st.erase(st.begin());
		}
		st.insert({As[i], A[i]});
	}
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:25:6: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   25 |  int x;
      |      ^

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	776 KB	Output is correct
2	Correct	3 ms	776 KB	Output is correct
3	Correct	2 ms	784 KB	Output is correct
4	Correct	4 ms	936 KB	Output is correct
5	Correct	5 ms	1168 KB	Output is correct
6	Correct	7 ms	1024 KB	Output is correct
7	Correct	8 ms	1140 KB	Output is correct
8	Correct	7 ms	1088 KB	Output is correct
9	Correct	6 ms	1088 KB	Output is correct
10	Correct	13 ms	1432 KB	Output is correct
11	Correct	8 ms	1088 KB	Output is correct

Subtask #2

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	1424 KB	Output is correct
2	Correct	74 ms	4096 KB	Output is correct
3	Correct	165 ms	10992 KB	Output is correct
4	Correct	87 ms	6648 KB	Output is correct
5	Correct	112 ms	6648 KB	Output is correct
6	Correct	129 ms	7408 KB	Output is correct
7	Correct	170 ms	9200 KB	Output is correct
8	Correct	115 ms	8952 KB	Output is correct
9	Correct	91 ms	6640 KB	Output is correct
10	Correct	173 ms	10480 KB	Output is correct

Subtask #3

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	6912 KB	Output is correct
2	Correct	163 ms	9712 KB	Output is correct
3	Correct	165 ms	9968 KB	Output is correct
4	Correct	170 ms	9968 KB	Output is correct
5	Correct	164 ms	9200 KB	Output is correct
6	Correct	165 ms	9968 KB	Output is correct
7	Correct	182 ms	9968 KB	Output is correct
8	Correct	145 ms	9968 KB	Output is correct
9	Correct	179 ms	9968 KB	Output is correct
10	Correct	182 ms	9968 KB	Output is correct

Subtask #4

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1124 KB	Output is correct
2	Correct	6 ms	1088 KB	Output is correct
3	Correct	6 ms	1168 KB	Output is correct
4	Correct	7 ms	1172 KB	Output is correct
5	Correct	5 ms	1088 KB	Output is correct
6	Correct	7 ms	1164 KB	Output is correct
7	Correct	7 ms	1088 KB	Output is correct
8	Correct	7 ms	1088 KB	Output is correct
9	Correct	8 ms	1088 KB	Output is correct
10	Correct	11 ms	1448 KB	Output is correct

Subtask #5

39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	8176 KB	Output is correct - 120000 bits used
2	Correct	162 ms	8432 KB	Output is correct - 122000 bits used
3	Correct	167 ms	8688 KB	Output is correct - 125000 bits used
4	Correct	164 ms	8688 KB	Output is correct - 125000 bits used
5	Correct	170 ms	8688 KB	Output is correct - 125000 bits used
6	Correct	164 ms	8624 KB	Output is correct - 125000 bits used
7	Correct	165 ms	8592 KB	Output is correct - 124828 bits used
8	Correct	167 ms	8688 KB	Output is correct - 124910 bits used
9	Correct	164 ms	8688 KB	Output is correct - 125000 bits used
10	Correct	143 ms	8944 KB	Output is correct - 125000 bits used