oj.uz

Submission #260445

# Submission time Handle Problem Language Result Execution time Memory
260445 2020-08-10T09:18:15 Z songc Library (JOI18_library) C++14
100 / 100
 619 ms 384 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

int N;
int R[1010];
vector<int> ans, Q;

void Solve(int n){
	N = n;
	if (N==1){
		ans.push_back(1);
		Answer(ans);
        return;
	}
	Q.resize(N);
	for (int i=0; i<N; i++) R[i] = i;
	for (int i=0; i<N; i++){
		for (int j=0; j<N; j++) Q[j] = (i==j)?0:1;
		if (Query(Q) == 1){
			ans.push_back(i);
			for (int j=i; j<N; j++) swap(R[j], R[j+1]);
			break;
		}
	}
	for (int i=N-2; i>0; i--){
		int l=0, h=i, k;
		while (l<=h){
			int m=l+h>>1;
			for (int j=0; j<N; j++) Q[j] = 0;
			for (int j=0; j<=m; j++) Q[R[j]] = 1;
			int x = Query(Q);
			Q[ans.back()] = 1;
			int y = Query(Q);
			if (x == y) k=m, h=m-1;
			else l=m+1;
		}
		ans.push_back(R[k]);
		for (int j=k; j<i; j++) swap(R[j], R[j+1]);
	}
	ans.push_back(R[0]);
	for (int &x : ans) x++;
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m=l+h>>1;
          ~^~
library.cpp:28:17: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int l=0, h=i, k;
                 ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 368 KB # of queries: 2399
2 Correct 51 ms 256 KB # of queries: 2435
3 Correct 36 ms 376 KB # of queries: 2656
4 Correct 36 ms 256 KB # of queries: 2595
5 Correct 39 ms 256 KB # of queries: 2524
6 Correct 34 ms 372 KB # of queries: 2563
7 Correct 59 ms 372 KB # of queries: 2554
8 Correct 51 ms 256 KB # of queries: 2422
9 Correct 60 ms 256 KB # of queries: 2548
10 Correct 30 ms 256 KB # of queries: 1486
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 1 ms 256 KB # of queries: 1
13 Correct 1 ms 256 KB # of queries: 4
14 Correct 1 ms 256 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 77
16 Correct 4 ms 256 KB # of queries: 193

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 368 KB # of queries: 2399
2 Correct 51 ms 256 KB # of queries: 2435
3 Correct 36 ms 376 KB # of queries: 2656
4 Correct 36 ms 256 KB # of queries: 2595
5 Correct 39 ms 256 KB # of queries: 2524
6 Correct 34 ms 372 KB # of queries: 2563
7 Correct 59 ms 372 KB # of queries: 2554
8 Correct 51 ms 256 KB # of queries: 2422
9 Correct 60 ms 256 KB # of queries: 2548
10 Correct 30 ms 256 KB # of queries: 1486
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 1 ms 256 KB # of queries: 1
13 Correct 1 ms 256 KB # of queries: 4
14 Correct 1 ms 256 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 77
16 Correct 4 ms 256 KB # of queries: 193
17 Correct 461 ms 384 KB # of queries: 18028
18 Correct 523 ms 380 KB # of queries: 17277
19 Correct 573 ms 376 KB # of queries: 17477
20 Correct 431 ms 376 KB # of queries: 16299
21 Correct 475 ms 376 KB # of queries: 15350
22 Correct 475 ms 376 KB # of queries: 17661
23 Correct 448 ms 256 KB # of queries: 17248
24 Correct 203 ms 380 KB # of queries: 7915
25 Correct 619 ms 380 KB # of queries: 17156
26 Correct 536 ms 376 KB # of queries: 16001
27 Correct 153 ms 376 KB # of queries: 8044
28 Correct 486 ms 376 KB # of queries: 15973
29 Correct 482 ms 376 KB # of queries: 15955
30 Correct 485 ms 376 KB # of queries: 15973