Submission #930886

#	Time	Username	Problem	Language	Result	Execution time	Memory
930886		daoquanglinh2007	Mouse (info1cup19_mouse)	C++17	100 / 100	38 ms	708 KiB

mouse

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

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <int> adj[305], circuit;
bool vis[305];

void dfs(int u){
	vis[u] = 1;
	circuit.push_back(u);
	for (int v : adj[u]){
		if (vis[v]) continue;
		dfs(v);
	}
}

void solve(int n){
	vector <int> q = {};
	for (int i = 1; i <= n; i++){
		q.push_back(i);
		adj[i].clear();
	}
	
	while (true){
		shuffle(q.begin(), q.end(), rng);
		int tmp = query(q);
		if (tmp == n) return;
		if (tmp == 0) break;
	}
	
	for (int t = 1; t <= n; t++){
		vector <pii> arr = {};
		for (int i = 1; i <= n; i++){
			int j = ((t-1-i+3)%n+n)%n;
			if (j == 0) j = n;
			if (i < j) arr.push_back(mp(i, j));
		}
		vector <int> q2 = q;
		for (pii p : arr) swap(q2[p.fi-1], q2[p.se-1]);
		int num = query(q2);
		if (num == n) return;
		int cur = -1, lst = 0;
		while (lst < num){
			int l = cur+1, r = isz(arr)-1, res = -1;
			int nw = -1;
			while (l <= r){
				int mid = (l+r)/2;
				q2 = q;
				for (int j = 0; j <= mid; j++)
					swap(q2[arr[j].fi-1], q2[arr[j].se-1]);
				int tmp = query(q2);
				if (tmp > lst){
					res = mid;
					nw = tmp;
					r = mid-1;
				}
				else l = mid+1;
			}
			adj[arr[res].fi].push_back(arr[res].se);
			adj[arr[res].se].push_back(arr[res].fi);
			cur = res;
			lst = nw;
		}
	}
	vector <int> p = q;
	memset(vis, 0, sizeof(vis));
	for (int u = 1; u <= n; u++){
		if (vis[u]) continue;
		circuit.clear();
		dfs(u);
		
		vector <int> q2 = q;
		for (int i = 0; i < isz(circuit); i++){
			int j = (i+1)%isz(circuit);
			q2[circuit[j]-1] = q[circuit[i]-1];
		}
		int tmp = query(q2);
		if (tmp == n) return;
		if (tmp < isz(circuit)) reverse(circuit.begin(), circuit.end());
		
		for (int i = 0; i < isz(circuit); i++){
			int j = (i+1)%isz(circuit);
			p[circuit[j]-1] = q[circuit[i]-1];
		}
	}
	query(p);
}

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