oj.uz

Submission #101124

# Submission time Handle Problem Language Result Execution time Memory
101124 2019-03-16T17:38:02 Z kdh9949 Library (JOI18_library) C++17
100 / 100
 488 ms 632 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int N = 1005;

static int n, chk[N], ans[N];
static vector<int> rep;

int ask(vector<int> v){
	vector<int> c(n, 0);
	for(int i : v) c[i - 1] = 1;
	return Query(c);
}

int ask(int x, int y){
	vector<int> v(n, 0);
	v[x - 1] = v[y - 1] = 1;
	return Query(v);
}

void f(vector<int> cv, vector<int> tv, int cnt){
	if(cv.size() == cnt){
		for(int i : cv) rep.push_back(i);
		return;
	}
	vector<int> cc(n + 1, 0);
	vector<int> lv, rv, rrv;
	for(int i = 0, j = 0; i < cv.size(); i++, j ^= 1){
		if(j) lv.push_back(cv[i]);
		else rv.push_back(cv[i]);
		cc[cv[i]] = 1;
	}
	rrv = rv;
	for(int i : tv) if(!cc[i]) rv.push_back(i);
	int la = ask(lv);
	int ra = ask(rv);
	if(cnt == 1){
		if(la == ra) f(lv, tv, 1);
		else f(rrv, tv, 1);
	}
	else{
		if(la > ra) f(lv, tv, 2);
		else if(la < ra) f(rrv, tv, 2);
		else{
			f(lv, tv, 1);
			f(rrv, tv, 1);
		}
	}
}

void Solve(int n){
	::n = n;
	for(int l = 0, r = n - 1; l < r; l++, r--){
		rep.clear();
		vector<int> v;
		for(int i = 1; i <= n; i++) if(!chk[i]) v.push_back(i);
		f(v, v, 2);
		if(l && ask(ans[l - 1], rep[0]) > 1) swap(rep[0], rep[1]);
		ans[l] = rep[0];
		ans[r] = rep[1];
		chk[rep[0]] = chk[rep[1]] = 1;
	}
	if(n & 1) for(int i = 1; i <= n; i++) if(!chk[i]) ans[n / 2] = i;
	Answer(vector<int>(ans, ans + n));
}

Compilation message

library.cpp: In function 'void f(std::vector<int>, std::vector<int>, int)':
library.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cv.size() == cnt){
     ~~~~~~~~~~^~~~~~
library.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < cv.size(); i++, j ^= 1){
                        ~~^~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 384 KB # of queries: 2147
2 Correct 33 ms 256 KB # of queries: 2106
3 Correct 32 ms 336 KB # of queries: 2197
4 Correct 40 ms 384 KB # of queries: 2241
5 Correct 31 ms 384 KB # of queries: 2269
6 Correct 44 ms 632 KB # of queries: 2227
7 Correct 26 ms 336 KB # of queries: 2239
8 Correct 33 ms 256 KB # of queries: 2133
9 Correct 45 ms 256 KB # of queries: 2184
10 Correct 20 ms 256 KB # of queries: 1279
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 0
13 Correct 2 ms 408 KB # of queries: 4
14 Correct 2 ms 256 KB # of queries: 7
15 Correct 3 ms 328 KB # of queries: 74
16 Correct 5 ms 384 KB # of queries: 160

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 384 KB # of queries: 2147
2 Correct 33 ms 256 KB # of queries: 2106
3 Correct 32 ms 336 KB # of queries: 2197
4 Correct 40 ms 384 KB # of queries: 2241
5 Correct 31 ms 384 KB # of queries: 2269
6 Correct 44 ms 632 KB # of queries: 2227
7 Correct 26 ms 336 KB # of queries: 2239
8 Correct 33 ms 256 KB # of queries: 2133
9 Correct 45 ms 256 KB # of queries: 2184
10 Correct 20 ms 256 KB # of queries: 1279
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 0
13 Correct 2 ms 408 KB # of queries: 4
14 Correct 2 ms 256 KB # of queries: 7
15 Correct 3 ms 328 KB # of queries: 74
16 Correct 5 ms 384 KB # of queries: 160
17 Correct 399 ms 444 KB # of queries: 15649
18 Correct 461 ms 384 KB # of queries: 15561
19 Correct 488 ms 356 KB # of queries: 15815
20 Correct 433 ms 356 KB # of queries: 14624
21 Correct 377 ms 384 KB # of queries: 13799
22 Correct 460 ms 444 KB # of queries: 15811
23 Correct 419 ms 384 KB # of queries: 15716
24 Correct 158 ms 344 KB # of queries: 7031
25 Correct 392 ms 512 KB # of queries: 15248
26 Correct 398 ms 428 KB # of queries: 14364
27 Correct 137 ms 384 KB # of queries: 7110
28 Correct 427 ms 384 KB # of queries: 17453
29 Correct 392 ms 432 KB # of queries: 15452
30 Correct 402 ms 432 KB # of queries: 17453