oj.uz

Submission #930886

# Submission time Handle Problem Language Result Execution time Memory
930886 2024-02-20T15:06:08 Z daoquanglinh2007 Mouse (info1cup19_mouse) C++17
100 / 100
 38 ms 708 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 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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 21
2 Correct 1 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 19
4 Correct 1 ms 596 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 21
6 Correct 0 ms 344 KB Correct! Number of queries: 23

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 21
2 Correct 1 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 19
4 Correct 1 ms 596 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 21
6 Correct 0 ms 344 KB Correct! Number of queries: 23
7 Correct 2 ms 448 KB Correct! Number of queries: 300
8 Correct 2 ms 448 KB Correct! Number of queries: 300
9 Correct 2 ms 448 KB Correct! Number of queries: 300
10 Correct 2 ms 444 KB Correct! Number of queries: 300
11 Correct 2 ms 444 KB Correct! Number of queries: 300
12 Correct 2 ms 452 KB Correct! Number of queries: 300
13 Correct 3 ms 444 KB Correct! Number of queries: 300
14 Correct 2 ms 448 KB Correct! Number of queries: 300
15 Correct 2 ms 448 KB Correct! Number of queries: 300
16 Correct 2 ms 444 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 21
2 Correct 1 ms 344 KB Correct! Number of queries: 10
3 Correct 0 ms 344 KB Correct! Number of queries: 19
4 Correct 1 ms 596 KB Correct! Number of queries: 21
5 Correct 0 ms 344 KB Correct! Number of queries: 21
6 Correct 0 ms 344 KB Correct! Number of queries: 23
7 Correct 2 ms 448 KB Correct! Number of queries: 300
8 Correct 2 ms 448 KB Correct! Number of queries: 300
9 Correct 2 ms 448 KB Correct! Number of queries: 300
10 Correct 2 ms 444 KB Correct! Number of queries: 300
11 Correct 2 ms 444 KB Correct! Number of queries: 300
12 Correct 2 ms 452 KB Correct! Number of queries: 300
13 Correct 3 ms 444 KB Correct! Number of queries: 300
14 Correct 2 ms 448 KB Correct! Number of queries: 300
15 Correct 2 ms 448 KB Correct! Number of queries: 300
16 Correct 2 ms 444 KB Correct! Number of queries: 300
17 Correct 36 ms 456 KB Correct! Number of queries: 2000
18 Correct 34 ms 700 KB Correct! Number of queries: 1900
19 Correct 34 ms 684 KB Correct! Number of queries: 1900
20 Correct 37 ms 688 KB Correct! Number of queries: 2000
21 Correct 35 ms 452 KB Correct! Number of queries: 2000
22 Correct 38 ms 688 KB Correct! Number of queries: 1900
23 Correct 35 ms 708 KB Correct! Number of queries: 2000
24 Correct 37 ms 684 KB Correct! Number of queries: 2000
25 Correct 37 ms 448 KB Correct! Number of queries: 2000
26 Correct 36 ms 684 KB Correct! Number of queries: 2000