Submission #422111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
422111	2021-06-09T17:52:18 Z	CSQ31	Mouse (info1cup19_mouse)	C++14	Compilation error	0 ms	0 KB

mouse

#include<bits/stdc++.h>
#include "permutation.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef vector<vector<ll>> VII;
typedef pair<int,int> pii;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>a;
vector<bool>unsolved;
vector<pii>swaps;
vector<pii>partition(){
	vector<int>s;
	for(int i=0;i<sz(unsolved);i++){
		if(!unsolved[i])s.pb(i);
	}
	shuffle(all(s),rng);
	vector<pii>res;
	for(int i=1;i<sz(s);i+=2)res.pb({s[i],s[i-1]});
	return res;
}
void swap_array(int l,int r){
	for(int i=l;i<=r;i++)swap(a[swaps[i].fi],a[swaps[i].se]);
	
}
void solve(int n){
	for(int i=1;i<=n;i++)a.pb(i);
	while(true){
		shuffle(all(a),rng);
		int res = query(a);
		if(res == n)return;
		if(!res)break;
	}
	//cout<<"derangement"<<'\n';
	//for(int x:a)cout<<x<<" ";
	//cout<<'\n';
	unsolved.assign(n,0); //what indexes have we solved
	int solved = 0;
	int cnt = 0;
	while(true){
		int cur=0;
		//for(int i=0;i<n;i++)cout<<a[i]<<" ";
		//cout<<'\n';
		//for(int i=0;i<n;i++)cout<<unsolved[i]<<" ";
		//cout<<'\n';
		while(true){ //random until find one that increases answer
			swaps = partition();
			swap_array(0,sz(swaps)-1);
			cur = query(a);
			swap_array(0,sz(swaps)-1);
			if(cur == n)return;
			if(cur > solved)break;
			cnt++;	
		}
		swap_array(0,sz(swaps)-1);
		int l = 0,r = sz(swaps)-1;
		int res = 0;
		while(r>l){
			int mid = (l+r)/2;
			swap_array(l,mid);
			res = query(a);
			swap_array(l,mid);
			if(res == n)return;
			if(res < cur)r = mid;
			else l = mid+1;
		}
		swap_array(0,sz(swaps)-1);
		swap_array(l,l);
		res = query(a);
		swap_array(l,l);
		//cout<<"thonk2"<<'\n';
		//for(int i=0;i<n;i++)cout<<a[i]<<" ";
		//cout<<'\n';
		if(res == solved+2){ //both are correct
			//cout<<"CASE 1:"<<swaps[l].fi<<" "<<swaps[l].se<<'\n';
			swap_array(l,l);
			unsolved[swaps[l].fi] = 1;
			unsolved[swaps[l].se] = 1;
			solved+=2;
		}else{//res == cur-1;
			//we have indexes a,b -> b,a
			//WLOG b is correct
			//case 1 : swap smtg with b if answer = solved,b is correct
			//case 2 : swap smtg with a 
			//subcase 1:answer = solved+1,b is correct /the other index apart from our choice
			//subcase 2:answer = solved+2,b is correct 
			//subcase 3:answer = solved+3,b c a is correct we solved three indexes
			int x = swaps[l].fi;
			int y = swaps[l].se;
			int z = -1;
			for(int i=0;i<n;i++){if(!unsolved[i] && i != x && i!=y){z=i;break;}}	
			swap(a[x],a[y]); // z,x,y
			swap(a[x],a[z]); //we have x,y -> y,x -> y,z,x 
			res = query(a);
			//cout<<x<<" "<<y<<" "<<z<<'\n';
			//cout<<solved<<" "<<res<<'\n';
			//for(int i=0;i<n;i++)cout<<a[i]<<" ";
			//cout<<'\n';
			if(res == n)return;
			if(res == solved){//index x is correct
			//	cout<<"CASE 2"<<'\n';
				swap(a[x],a[z]);
				solved++;
				unsolved[x] = 1;
			}else if(res <= solved+2){//index y is correct
				//cout<<"CASE 3"<<'\n';
				swap(a[x],a[z]);
				solved++;
				unsolved[y] = 1;
			}else{
				//cout<<"CASE 4"<<'\n';
				solved+=3;
				unsolved[x] = unsolved[y] = unsolved[z] = 1;
				
			}
		}
	
	}
}

Compilation message

mouse.cpp:2:10: fatal error: permutation.h: No such file or directory
    2 | #include "permutation.h"
      |          ^~~~~~~~~~~~~~~
compilation terminated.