Submission #413766

#	Time	Username	Problem	Language	Result	Execution time	Memory
413766		oolimry	Mouse (info1cup19_mouse)	C++17	100 / 100	106 ms	296 KiB

mouse

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

int solved[260];

void solve(int n) {
	srand(time(NULL));
	vector<int> best;
	for(int i = 1; i <= n; i++) best.push_back(i);
	
	while(true){
		random_shuffle(all(best));
		if(query(best) == 0) break;
	}
	
	vector<int> unknown;
	
	
	int cur = 0;
	
	int known = -1;
	while(true){
		unknown.clear();
		for(int i = 0; i < n; i++){
			if(not solved[i]) unknown.push_back(i);
			else known = i;
		}
		random_shuffle(all(unknown));
		vector<int> test;
		for(int x : best) test.push_back(x);
		
		for(int i = 0;i+1 < sz(unknown);i += 2){
			swap(test[unknown[i]], test[unknown[i+1]]);
		}
		
		int nxt = query(test);
		if(nxt == n) return;
		if(nxt == cur) continue;
		
		if(nxt > cur){
			//cout << "U: "; for(int x : unknown) cout << x << " "; cout << endl;
			////cout << "P: "; for(int i = 0;i < n;i++) cout << i << " "; cout << endl;
			//cout << "B: "; for(int x : best) cout << x << " "; cout << endl;
			int low = -1; int high = sz(unknown)/2 - 1;
			
			while(low != high-1){
				int mid = (low+high)/2;
				test.clear(); for(int x : best) test.push_back(x);
				for(int i = 0;i <= mid;i++){
					swap(test[unknown[i*2]], test[unknown[i*2+1]]);
				}
				
				int res = query(test);
				if(res == n) return;
				if(res > cur) high = mid;
				else low = mid;
			}
			
			
			int a = unknown[high*2], b = unknown[high*2+1];
			swap(best[a], best[b]);
			int newcur = query(best);
			if(newcur == n) return;
			
			if(newcur - cur == 2){
				solved[a] = 1;
				solved[b] = 1;
			}
			else{
				if(known == -1){
					int x = 1;
					while(x == a or x == b) x++;
					
					vector<int> test; for(int x : best) test.push_back(x);
					swap(test[x], test[a]);
					if(query(test) < newcur) solved[a] = 1;
					else solved[b] = 1;
				}
				else{
					vector<int> test; for(int x : best) test.push_back(x);
					swap(test[known], test[a]);

					if(query(test) == newcur-1) solved[b] = 1;
					else solved[a] = 1;
				}
			}

			cur = newcur;
			
		}
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49