oj.uz

Submission #98187

# Submission time Handle Problem Language Result Execution time Memory
98187 2019-02-21T10:48:20 Z onjo0127 Library (JOI18_library) C++11
100 / 100
 521 ms 512 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

vector<int> M;

void Solve(int N) {
    if(N == 1) {
        Answer(vector<int>(1, 1));
        return;
    }
	int now;
	M = vector<int>(N, 1);
	for(int i=0; i<N; i++) {
        M[i] = 0;
        if(Query(M) == 1) now = i;
        M[i] = 1;
	}
	M = vector<int>(N, 0);
	vector<int> S, ans = {now + 1};
	for(int i=0; i<N; i++) if(i != now) S.push_back(i);
	for(int i=0; i<N-1; i++) {
        int l = 0, r = N-i-1;
        while(l < r) {
            int m = l+r >> 1;
            for(int i=l; i<=m; i++) M[S[i]] = 1;
            int pr = Query(M);
            M[now] = 1;
            bool f = (pr != Query(M));
            M[now] = 0;
            for(int i=l; i<=m; i++) M[S[i]] = 0;
            if(f) l = m+1;
            else r = m;
        }
        now = S[l];
        ans.push_back(S[l] + 1);
        S.erase(S.begin() + l);
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l+r >> 1;
                     ~^~
library.cpp:22:25: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(int i=0; i<N; i++) if(i != now) S.push_back(i);
                         ^~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB # of queries: 2584
2 Correct 35 ms 384 KB # of queries: 2571
3 Correct 52 ms 256 KB # of queries: 2730
4 Correct 43 ms 328 KB # of queries: 2718
5 Correct 44 ms 384 KB # of queries: 2720
6 Correct 43 ms 384 KB # of queries: 2708
7 Correct 37 ms 384 KB # of queries: 2722
8 Correct 44 ms 384 KB # of queries: 2599
9 Correct 37 ms 384 KB # of queries: 2711
10 Correct 17 ms 408 KB # of queries: 1589
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 2 ms 256 KB # of queries: 14
15 Correct 5 ms 384 KB # of queries: 99
16 Correct 5 ms 384 KB # of queries: 219

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB # of queries: 2584
2 Correct 35 ms 384 KB # of queries: 2571
3 Correct 52 ms 256 KB # of queries: 2730
4 Correct 43 ms 328 KB # of queries: 2718
5 Correct 44 ms 384 KB # of queries: 2720
6 Correct 43 ms 384 KB # of queries: 2708
7 Correct 37 ms 384 KB # of queries: 2722
8 Correct 44 ms 384 KB # of queries: 2599
9 Correct 37 ms 384 KB # of queries: 2711
10 Correct 17 ms 408 KB # of queries: 1589
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 4
13 Correct 2 ms 384 KB # of queries: 9
14 Correct 2 ms 256 KB # of queries: 14
15 Correct 5 ms 384 KB # of queries: 99
16 Correct 5 ms 384 KB # of queries: 219
17 Correct 512 ms 324 KB # of queries: 18208
18 Correct 505 ms 504 KB # of queries: 17957
19 Correct 470 ms 376 KB # of queries: 18194
20 Correct 478 ms 376 KB # of queries: 16964
21 Correct 457 ms 320 KB # of queries: 15953
22 Correct 513 ms 332 KB # of queries: 18162
23 Correct 521 ms 384 KB # of queries: 18167
24 Correct 184 ms 376 KB # of queries: 8339
25 Correct 445 ms 324 KB # of queries: 17739
26 Correct 420 ms 512 KB # of queries: 16541
27 Correct 219 ms 384 KB # of queries: 8287
28 Correct 433 ms 328 KB # of queries: 17950
29 Correct 425 ms 448 KB # of queries: 17929
30 Correct 480 ms 328 KB # of queries: 17950