oj.uz

Submission #369725

# Submission time Handle Problem Language Result Execution time Memory
369725 2021-02-22T09:12:00 Z nafis_shifat Library (JOI18_library) C++14
19 / 100
 443 ms 392 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=1e5+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(true) {
				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 {

			}
		}



		ans.push_back(val);
		cnt[val] = true;
		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:84:8: warning: unused variable 'x' [-Wunused-variable]
   84 |    int x = (prev >> j) & 1;
      |        ^
library.cpp:85:8: warning: unused variable 'y' [-Wunused-variable]
   85 |    int y = (cur >> j) & 1;
      |        ^
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 61 ms 364 KB # of queries: 3451
2 Correct 59 ms 364 KB # of queries: 3472
3 Correct 64 ms 364 KB # of queries: 3715
4 Correct 58 ms 364 KB # of queries: 3658
5 Correct 52 ms 364 KB # of queries: 3579
6 Correct 44 ms 384 KB # of queries: 3632
7 Correct 66 ms 364 KB # of queries: 3637
8 Correct 45 ms 364 KB # of queries: 3476
9 Correct 64 ms 364 KB # of queries: 3610
10 Correct 37 ms 364 KB # of queries: 2332
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 12
13 Correct 1 ms 364 KB # of queries: 26
14 Correct 1 ms 364 KB # of queries: 37
15 Correct 5 ms 364 KB # of queries: 194
16 Correct 5 ms 364 KB # of queries: 394

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 364 KB # of queries: 3451
2 Correct 59 ms 364 KB # of queries: 3472
3 Correct 64 ms 364 KB # of queries: 3715
4 Correct 58 ms 364 KB # of queries: 3658
5 Correct 52 ms 364 KB # of queries: 3579
6 Correct 44 ms 384 KB # of queries: 3632
7 Correct 66 ms 364 KB # of queries: 3637
8 Correct 45 ms 364 KB # of queries: 3476
9 Correct 64 ms 364 KB # of queries: 3610
10 Correct 37 ms 364 KB # of queries: 2332
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 12
13 Correct 1 ms 364 KB # of queries: 26
14 Correct 1 ms 364 KB # of queries: 37
15 Correct 5 ms 364 KB # of queries: 194
16 Correct 5 ms 364 KB # of queries: 394
17 Runtime error 443 ms 392 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -