Submission #930871

# Submission time Handle Problem Language Result Execution time Memory
930871 2024-02-20T14:48:59 Z daoquanglinh2007 Mouse (info1cup19_mouse) C++17
Compilation error
0 ms 0 KB
#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 findPermutation(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;
		for (int i = 1; i <= num; i++){
			int l = cur+1, r = isz(arr)-2, res = isz(arr)-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]);	
				if (query(q2) >= i){
					res = mid;
					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;
		}
	}
	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);
}

Compilation message

/usr/bin/ld: /tmp/ccEQ4pEX.o: in function `main':
grader.cpp:(.text.startup+0x30): undefined reference to `solve(int)'
collect2: error: ld returned 1 exit status