oj.uz

Submission #274818

# Submission time Handle Problem Language Result Execution time Memory
274818 2020-08-19T16:13:46 Z amoo_safar Last supper (IOI12_supper) C++17
100 / 100
 182 ms 10992 KB 
// 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

*/
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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