oj.uz

Submission #230745

# Submission time Handle Problem Language Result Execution time Memory
230745 2020-05-11T14:17:46 Z Dilshod_Imomov Library (JOI18_library) C++17
100 / 100
 444 ms 384 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
 
const int N = 1e3 + 7;

void Solve(int n)
{
	vector < int > M(n, 1), res(n), vc(n);
	if ( n == 1 ) {
		res[0] = 1;
		Answer(res);
		return;
	}  
	int left = 0;
	for ( ; left < n; left++ ) {
		M[left] = 0;
		if ( Query(M) == 1 ) {
			break;
		}
		M[left] = 1;
	}
	res[0] = left + 1;
	int ind = 0;
	for ( int i = 0; i < n; i++ ) {
		if ( i != left ) {
			vc[ind++] = i + 1;
		}
	}
	// for ( int i = 0; i < ind; i++ ) {
	// 	cout << vc[i] << ' ';
	// }
	// cout << '\n';
	fill( M.begin(), M.end(), 0 );
	for ( int i = 1; i < n; i++ ) {
		// for ( int j = 0; j < ind - 1; j++ ) {
		// 	cout << vc[j] << ' ';
		// }
		// cout << '\n';
		int l = 0, r = ind - 1, md, ans = 0;
		// cout << i << '\n';
		while ( r - l >= 1 ) {
			md = (l + r) / 2;
			// cout << l << ' ' << md << ' ' << r << '\n';
			for ( int j = l; j <= md; j++ ) {
				M[vc[j] - 1] = 1;
			}
			// for ( auto j: M ) {
			// 	cout << j << ' ';	
			// }
			// cout << '\n';
			int res1 = Query(M);
			M[res[i - 1] - 1] = 1;
			// for ( auto j: M ) {
			// 	cout << j << ' ';
			// }
			// cout << '\n';
			int res2 = Query(M);
			for ( int j = l; j <= md; j++ ) {
				M[vc[j] - 1] = 0;
			}
			M[res[i - 1] - 1] = 0;
			if ( res1 == res2 ) {
				r = md;
				ans = md;
			}
			else {
				l = md + 1;
			}
		}
		res[i] = vc[l];
		// cout << vc[l] << " --------------\n";
		swap( vc[l], vc[ind - 1] );
		ind--;
	}
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:40:31: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   int l = 0, r = ind - 1, md, ans = 0;
                               ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 256 KB # of queries: 2373
2 Correct 40 ms 384 KB # of queries: 2423
3 Correct 44 ms 384 KB # of queries: 2646
4 Correct 43 ms 256 KB # of queries: 2585
5 Correct 45 ms 256 KB # of queries: 2498
6 Correct 44 ms 256 KB # of queries: 2551
7 Correct 45 ms 256 KB # of queries: 2560
8 Correct 44 ms 256 KB # of queries: 2438
9 Correct 42 ms 256 KB # of queries: 2532
10 Correct 25 ms 256 KB # of queries: 1448
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 4 ms 256 KB # of queries: 1
13 Correct 4 ms 384 KB # of queries: 4
14 Correct 4 ms 256 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 77
16 Correct 8 ms 256 KB # of queries: 181

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 256 KB # of queries: 2373
2 Correct 40 ms 384 KB # of queries: 2423
3 Correct 44 ms 384 KB # of queries: 2646
4 Correct 43 ms 256 KB # of queries: 2585
5 Correct 45 ms 256 KB # of queries: 2498
6 Correct 44 ms 256 KB # of queries: 2551
7 Correct 45 ms 256 KB # of queries: 2560
8 Correct 44 ms 256 KB # of queries: 2438
9 Correct 42 ms 256 KB # of queries: 2532
10 Correct 25 ms 256 KB # of queries: 1448
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 4 ms 256 KB # of queries: 1
13 Correct 4 ms 384 KB # of queries: 4
14 Correct 4 ms 256 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 77
16 Correct 8 ms 256 KB # of queries: 181
17 Correct 444 ms 256 KB # of queries: 18026
18 Correct 395 ms 384 KB # of queries: 17253
19 Correct 417 ms 384 KB # of queries: 17399
20 Correct 347 ms 384 KB # of queries: 16293
21 Correct 343 ms 256 KB # of queries: 15320
22 Correct 418 ms 384 KB # of queries: 17661
23 Correct 419 ms 384 KB # of queries: 17232
24 Correct 144 ms 256 KB # of queries: 7877
25 Correct 410 ms 256 KB # of queries: 17052
26 Correct 381 ms 384 KB # of queries: 15989
27 Correct 144 ms 384 KB # of queries: 8000
28 Correct 409 ms 384 KB # of queries: 16581
29 Correct 383 ms 256 KB # of queries: 16533
30 Correct 397 ms 384 KB # of queries: 16581