Submission #100769

# Submission time Handle Problem Language Result Execution time Memory
100769 2019-03-14T08:58:29 Z JPN20 Library (JOI18_library) C++17
100 / 100
542 ms 428 KB
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

int c = 0, N; bool used[1009];

int getans(int pos) {
	vector<int>vec;
	for (int i = 0; i < N; i++) {
		if (used[i] == false) vec.push_back(i);
	}
	
	int sz = 1, cc = 0; while (sz <= vec.size()) { sz *= 2; cc++; }
	
	int cx = 0;
	for (int i = cc - 1; i >= 0; i--) {
		vector<int>V1(N, 0);
		for (int j = 0; j < cx + (1 << i); j++) {
			if (j >= vec.size()) break;
			V1[vec[j]] = 1;
		}
		vector<int>V2 = V1; V2[c] = 1;
		
		int F1 = Query(V1);
		int F2 = Query(V2);
		if (F1 != F2) cx += (1 << i);
	}
	return vec[cx];
}

void Solve(int NN) {
	if (NN == 1) {
		Answer({1});
		return;
	}
	N = NN;
	for (int i = 0; i < N; i++) {
		vector<int>G(N, 1); G[i] = 0;
		int Z = Query(G);
		if (Z == 1) { c = i; }
	}
	
	vector<int>W;
	used[c] = true; W.push_back(c + 1);
	
	for (int i = 0; i < N - 1; i++) {
		int f = getans(c);
		W.push_back(f + 1);
		used[f] = true;
		c = f;
	}
	Answer(W);
}

Compilation message

library.cpp: In function 'int getans(int)':
library.cpp:13:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int sz = 1, cc = 0; while (sz <= vec.size()) { sz *= 2; cc++; }
                             ~~~^~~~~~~~~~~~~
library.cpp:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j >= vec.size()) break;
        ~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 49 ms 428 KB # of queries: 2754
2 Correct 43 ms 256 KB # of queries: 2737
3 Correct 56 ms 384 KB # of queries: 2890
4 Correct 62 ms 384 KB # of queries: 2890
5 Correct 39 ms 384 KB # of queries: 2890
6 Correct 38 ms 252 KB # of queries: 2890
7 Correct 42 ms 328 KB # of queries: 2890
8 Correct 29 ms 256 KB # of queries: 2771
9 Correct 30 ms 320 KB # of queries: 2873
10 Correct 23 ms 428 KB # of queries: 1683
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 256 KB # of queries: 9
14 Correct 2 ms 384 KB # of queries: 14
15 Correct 3 ms 384 KB # of queries: 105
16 Correct 7 ms 256 KB # of queries: 235
# Verdict Execution time Memory Grader output
1 Correct 49 ms 428 KB # of queries: 2754
2 Correct 43 ms 256 KB # of queries: 2737
3 Correct 56 ms 384 KB # of queries: 2890
4 Correct 62 ms 384 KB # of queries: 2890
5 Correct 39 ms 384 KB # of queries: 2890
6 Correct 38 ms 252 KB # of queries: 2890
7 Correct 42 ms 328 KB # of queries: 2890
8 Correct 29 ms 256 KB # of queries: 2771
9 Correct 30 ms 320 KB # of queries: 2873
10 Correct 23 ms 428 KB # of queries: 1683
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 256 KB # of queries: 9
14 Correct 2 ms 384 KB # of queries: 14
15 Correct 3 ms 384 KB # of queries: 105
16 Correct 7 ms 256 KB # of queries: 235
17 Correct 434 ms 384 KB # of queries: 18954
18 Correct 480 ms 424 KB # of queries: 18723
19 Correct 423 ms 316 KB # of queries: 18954
20 Correct 438 ms 384 KB # of queries: 17736
21 Correct 401 ms 256 KB # of queries: 16707
22 Correct 528 ms 256 KB # of queries: 18954
23 Correct 459 ms 256 KB # of queries: 18933
24 Correct 130 ms 320 KB # of queries: 8727
25 Correct 542 ms 376 KB # of queries: 18513
26 Correct 358 ms 376 KB # of queries: 17337
27 Correct 169 ms 384 KB # of queries: 8687
28 Correct 414 ms 256 KB # of queries: 18954
29 Correct 392 ms 404 KB # of queries: 18933
30 Correct 472 ms 384 KB # of queries: 18954