oj.uz

Submission #369802

# Submission time Handle Problem Language Result Execution time Memory
369802 2021-02-22T12:45:25 Z nafis_shifat Library (JOI18_library) C++14
100 / 100
 447 ms 648 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#include "library.h"
using namespace std;
using namespace std;
const int mxn=1e3+5;
const int inf=1e9;
vector<int> ans;
bool cnt[mxn] = {};

int get(vector<int> x) {
	bool f[mxn] = {};
	for(int i : x) if(cnt[i]) f[i] = true;
	bool last = false; 
    int r = 0;
    for(int i = 0; i < ans.size(); i++) {
    	int y = ans[i];
    	if(!f[y]) {
    		last = false;
    		continue;
    	}
    	if(!last) {
    		r++;
    		last = true;
    	}
    }
    return r;

}

int query(vector<int> M) {
	bool f = false;
	for(int i : M) if(i == 1) f = true;
	if(!f) return 0;
    int x = Query(M);
    return x;
}
void Solve(int n) {
	int start;

	vector<int> M(n);
	for(int i = 0; i < n; i++) M[i] = 1;

	for(int i = 1; i <= n; i++) {
		M[i - 1] = 0;
		int x = query(M);
		if(x == 1) {
			start = i;
			break;
		}
		M[i - 1] = 1;
	}



	int prev = 0;
	int cur = start;

	
	ans.push_back(cur);
	cnt[cur] = true;


	int pre[11][2];
	for(int i = 0; i < 10; i++) {
		vector<int> A(n),B(n);
		for(int j = 1; j <= n; j++) {
			if((j >> i) & 1) {
				A[j - 1] = 1;
				B[j - 1] = 0;
			} else {
				A[j - 1] = 0;
				B[j - 1] = 1;
			}
		}
		pre[i][0] = query(B);
		pre[i][1] = query(A);
	}
	for(int i = 1; i < n; i++) {
		int val = 0;
		for(int j = 0; j < 10; j++) {
			int x = (prev >> j) & 1;
			int y = (cur >> j) & 1;
			if(x == y) {
				vector<int> A(n);
				for(int k = 1; k <= n; k++) {
					if(cnt[k]) continue;
					if((k >> j) & 1) {
						A[k - 1] = 1;
					} else {
						A[k - 1] = 0;
					}
				}
				int r1 = query(A);
				A[cur - 1] = 1;
				int r2 = query(A);
				if(r1 == r2 && r1 != 0) {
					val |= 1 << j;
				}
			} else {
				vector<int> A(n);
				for(int k = 1; k <= n; k++) {
					if(cnt[k]) continue;
					if(((k >> j) & 1) == x) {
						A[k - 1] = 1;
					} else {
						A[k - 1] = 0;
					}
				}
				A[cur - 1] = 1;
				int r1 = query(A);
				vector<int> tmp;
				for(int k = 1; k <= n; k++) {
					if(cnt[k] && ((k >> j) & 1) == x) tmp.push_back(k);
				}
				int r2 = pre[j][x] - get(tmp);
				if(r1 == r2) {
					val |= (x * (1 << j));
				} else  {
					val |= ((1 - x) * (1 << j));
				}

			}

		}
		ans.push_back(val);
		cnt[val] = true;
		prev = cur;
		cur = val;
	}



	Answer(ans);

}

Compilation message

library.cpp: In function 'int get(std::vector<int>)':
library.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < ans.size(); i++) {
      |                    ~~^~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:40:6: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |  int start;
      |      ^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 364 KB # of queries: 2740
2 Correct 38 ms 504 KB # of queries: 2775
3 Correct 44 ms 364 KB # of queries: 2958
4 Correct 49 ms 364 KB # of queries: 2917
5 Correct 41 ms 364 KB # of queries: 2829
6 Correct 40 ms 364 KB # of queries: 2863
7 Correct 33 ms 496 KB # of queries: 2886
8 Correct 44 ms 364 KB # of queries: 2736
9 Correct 46 ms 364 KB # of queries: 2865
10 Correct 34 ms 380 KB # of queries: 1927
11 Correct 1 ms 364 KB # of queries: 10
12 Correct 1 ms 364 KB # of queries: 24
13 Correct 1 ms 364 KB # of queries: 35
14 Correct 1 ms 364 KB # of queries: 48
15 Correct 4 ms 364 KB # of queries: 182
16 Correct 9 ms 364 KB # of queries: 333

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 364 KB # of queries: 2740
2 Correct 38 ms 504 KB # of queries: 2775
3 Correct 44 ms 364 KB # of queries: 2958
4 Correct 49 ms 364 KB # of queries: 2917
5 Correct 41 ms 364 KB # of queries: 2829
6 Correct 40 ms 364 KB # of queries: 2863
7 Correct 33 ms 496 KB # of queries: 2886
8 Correct 44 ms 364 KB # of queries: 2736
9 Correct 46 ms 364 KB # of queries: 2865
10 Correct 34 ms 380 KB # of queries: 1927
11 Correct 1 ms 364 KB # of queries: 10
12 Correct 1 ms 364 KB # of queries: 24
13 Correct 1 ms 364 KB # of queries: 35
14 Correct 1 ms 364 KB # of queries: 48
15 Correct 4 ms 364 KB # of queries: 182
16 Correct 9 ms 364 KB # of queries: 333
17 Correct 420 ms 524 KB # of queries: 15932
18 Correct 377 ms 492 KB # of queries: 15193
19 Correct 424 ms 492 KB # of queries: 15323
20 Correct 345 ms 628 KB # of queries: 14347
21 Correct 368 ms 648 KB # of queries: 13714
22 Correct 447 ms 396 KB # of queries: 15409
23 Correct 412 ms 620 KB # of queries: 15051
24 Correct 160 ms 504 KB # of queries: 7842
25 Correct 359 ms 492 KB # of queries: 15070
26 Correct 374 ms 492 KB # of queries: 14198
27 Correct 173 ms 364 KB # of queries: 7669
28 Correct 407 ms 492 KB # of queries: 18001
29 Correct 396 ms 620 KB # of queries: 17978
30 Correct 350 ms 432 KB # of queries: 18001