oj.uz

Submission #25952

# Submission time Handle Problem Language Result Execution time Memory
25952 2017-06-25T07:54:05 Z kajebiii Carnival (CEOI14_carnival) C++14
100 / 100
 16 ms 2072 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 155;
const bool DEBUG = false;

int N, Nr[MAX_N], C, Ans[MAX_N];
int query(vector<int> &q) {
	printf("%d ", SZ(q));
	for(int x : q) printf("%d ", x); puts("");
	fflush(stdout);
	int res = 0;
	if(DEBUG) {
		set<int> S;
		for(int x : q) S.insert(Nr[x]);
		res = SZ(S);
	} else {
		scanf("%d", &res);
	}
	return res;
}

vector<int> List[MAX_N * 10]; pi It[MAX_N * 10];
vector<bool> chk;
vector<int> idx;
void findAns(int il, int ir) {
	bool isOne = true;
	vector<int> all;
	chk = vector<bool>(N+1, false);
	idx = vector<int>(N+1, -1);
	for(int i=il; i<=ir; i++) {
		if(SZ(List[i]) == 0) continue;
		if(It[i].two != It[i].one) isOne = false;
		vector<int> &nr = List[i];
		// 1 to It[i].two - It[i].one + 1
		int diff = (It[i].two - It[i].one + 2) / 2;
		int ix = -1;
		for(int l=0, r=SZ(nr)-1; l<=r; ) {
			int m = (l+r) >> 1;
			vector<int> q;
			for(int k=0; k<=m; k++) q.push_back(nr[k]);
			int c = query(q);
			if(c == diff) {
				ix = m;
				break;
			}else if(c < diff) l = m+1;
			else r = m-1;
		}
		for(int k=0; k<=ix; k++) {
			all.push_back(nr[k]);
			List[i*2].push_back(nr[k]);
			chk[nr[k]] = true;
		}
		for(int x : List[i]) idx[x] = i;
		It[i*2] = pi(It[i].one, It[i].one + diff-1);
		It[i*2+1] = pi(It[i].one + diff, It[i].two);
	}
	if(isOne) {
		for(int i=il; i<=ir; i++) for(int x : List[i]) Ans[x] = It[i].one;
		return;
	}

	int allC = query(all);
	for(int i=1; i<=N; i++) if(chk[i] == false) {
		all.push_back(i);
		int nowC = query(all);
		all.pop_back();
		if(allC == nowC) List[idx[i] * 2].push_back(i);
		else List[idx[i] * 2 + 1].push_back(i);
	}
	findAns(il*2, ir*2+1);
}
int main() {
	scanf("%d", &N);
	if(DEBUG) REPO(i, N) scanf("%d", &Nr[i]);

	vector<int> all; REPO(i, N) all.push_back(i);
	C = query(all);

	List[1] = all;
	It[1] = pi(1, C);
	findAns(1, 1);

	printf("0 ");
	for(int i=1; i<=N; i++) printf("%d ", Ans[i]);
	fflush(stdout);
	return 0;
}

Compilation message

carnival.cpp: In function 'int query(std::vector<int>&)':
carnival.cpp:30:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &res);
                    ^
carnival.cpp: In function 'int main()':
carnival.cpp:86:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
carnival.cpp:87:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  if(DEBUG) REPO(i, N) scanf("%d", &Nr[i]);
                                          ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 9 ms 2072 KB Output is correct
3 Correct 9 ms 2072 KB Output is correct
4 Correct 9 ms 2072 KB Output is correct
5 Correct 3 ms 2072 KB Output is correct
6 Correct 3 ms 2072 KB Output is correct
7 Correct 3 ms 2072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2072 KB Output is correct
2 Correct 6 ms 2072 KB Output is correct
3 Correct 9 ms 2072 KB Output is correct
4 Correct 6 ms 2072 KB Output is correct
5 Correct 3 ms 2072 KB Output is correct
6 Correct 6 ms 2072 KB Output is correct
7 Correct 3 ms 2072 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 6 ms 2072 KB Output is correct
3 Correct 6 ms 2072 KB Output is correct
4 Correct 6 ms 2072 KB Output is correct
5 Correct 3 ms 2072 KB Output is correct
6 Correct 0 ms 2072 KB Output is correct
7 Correct 6 ms 2072 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 3 ms 2072 KB Output is correct
3 Correct 13 ms 2072 KB Output is correct
4 Correct 16 ms 2072 KB Output is correct
5 Correct 3 ms 2072 KB Output is correct
6 Correct 9 ms 2072 KB Output is correct
7 Correct 13 ms 2072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 3 ms 2072 KB Output is correct
3 Correct 16 ms 2072 KB Output is correct
4 Correct 6 ms 2072 KB Output is correct
5 Correct 0 ms 2072 KB Output is correct
6 Correct 6 ms 2072 KB Output is correct
7 Correct 3 ms 2072 KB Output is correct