Submission #369802

#	Time	Username	Problem	Language	Result	Execution time	Memory
369802		nafis_shifat	Library (JOI18_library)	C++14	100 / 100	447 ms	648 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81