Submission #522457

#	Time	Username	Problem	Language	Result	Execution time	Memory
522457		amunduzbaev	Mouse (info1cup19_mouse)	C++17	Compilation error	0 ms	0 KiB

mouse

//~ #include "grader.h"

#include <bits/stdc++.h>
using namespace std;

#define ar array

int n, tot;
vector<int> todo, a, B;

//~ int query(vector<int> a){
	//~ assert((int)a.size() == n);
	//~ int res = 0;
	//~ for(int i=0;i<n;i++){
		//~ res += (a[i] == B[i]);
	//~ } tot++;
	//~ if(tot > 2400){
		//~ assert(false);
	//~ }
	//~ if(res == n){
		//~ cout<<"YES\n";
		//~ exit(0);
	//~ }
	//~ return res;
//~ }

int check(int x){
	assert(2 * x <= (int)todo.size());
	for(int i=0;i<x;i++){
		swap(a[todo[i<<1]], a[todo[i<<1|1]]);
	}
	
	int r = query(a);
	if(r == n) exit(0);
	for(int i=0;i<x;i++){
		swap(a[todo[i<<1]], a[todo[i<<1|1]]);
	} return r;
}

void solve(int N) { n = N;
	mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	
	a.resize(n);
	iota(a.begin(), a.end(), 1);
	while(1){
		shuffle(a.begin(), a.end(), rnd);
		int q = query(a);
		if(q == n) return;
		if(!q) break;
	}
	
	vector<int> used(n);
	int don = 0;
	while(1){
		//~ for(int i=0;i<n;i++){
			//~ cout<<used[i]<<" ";
		//~ } cout<<endl;
		//~ for(int i=0;i<n;i++){
			//~ cout<<a[i]<<" ";
		//~ } cout<<endl;
		
		todo.clear();
		for(int i=0;i<n;i++){
			if(used[i]) continue;
			todo.push_back(i);
		}
		
		shuffle(todo.begin(), todo.end(), rnd);
		int half = (int)todo.size() / 2;
		if(check(half) == don) continue;
		//~ cout<<"here"<<endl;
		int l = 1, r = half;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m) > don){
				r = m;
			} else {
				l = m + 1;
			}
		} l--;
		int i = todo[l<<1], j = todo[l<<1|1];
		swap(a[i], a[j]);
		int cost = query(a);
		if(cost == n) return;
		if(cost == don + 2){
			used[i] = used[j] = 1; don += 2;
		} else {
			int p = -1;
			for(int l=0;l<n;l++){
				if(used[l] || i == l || j == l) continue;
				p = l; break;
			}
			
			assert(~p);
			swap(a[i], a[p]);
			int tmp = query(a);
			if(tmp == n) return;
			swap(a[i], a[p]);
			if(tmp < cost) used[i] = 1;
			else used[j] = 1;
			don++;
		}
	}
}

/*

8
3 6 5 7 8 1 4 2

*/

//~ signed main(){
	//~ int n; cin>>n;
	//~ B.resize(n);
	//~ for(int i=0;i<n;i++) cin>>B[i];
	//~ solve(n);
//~ }

Compilation message (stderr)

mouse.cpp: In function 'int check(int)':
mouse.cpp:33:10: error: 'query' was not declared in this scope
   33 |  int r = query(a);
      |          ^~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:47:11: error: 'query' was not declared in this scope
   47 |   int q = query(a);
      |           ^~~~~
mouse.cpp:83:14: error: 'query' was not declared in this scope
   83 |   int cost = query(a);
      |              ^~~~~