oj.uz

Submission #522458

# Submission time Handle Problem Language Result Execution time Memory
522458 2022-02-05T04:18:07 Z amunduzbaev Mouse (info1cup19_mouse) C++17
100 / 100
 71 ms 200 KB 
#include "grader.h"

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

#define ar array

int n, tot;
vector<int> todo, a, B;

//~ int query(vector<int> a){
	//~ assert((int)a.size() == n);
	//~ int res = 0;
	//~ for(int i=0;i<n;i++){
		//~ res += (a[i] == B[i]);
	//~ } tot++;
	//~ if(tot > 2400){
		//~ assert(false);
	//~ }
	//~ if(res == n){
		//~ cout<<"YES\n";
		//~ exit(0);
	//~ }
	//~ return res;
//~ }

int check(int x){
	assert(2 * x <= (int)todo.size());
	for(int i=0;i<x;i++){
		swap(a[todo[i<<1]], a[todo[i<<1|1]]);
	}
	
	int r = query(a);
	if(r == n) exit(0);
	for(int i=0;i<x;i++){
		swap(a[todo[i<<1]], a[todo[i<<1|1]]);
	} return r;
}

void solve(int N) { n = N;
	mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	
	a.resize(n);
	iota(a.begin(), a.end(), 1);
	while(1){
		shuffle(a.begin(), a.end(), rnd);
		int q = query(a);
		if(q == n) return;
		if(!q) break;
	}
	
	vector<int> used(n);
	int don = 0;
	while(1){
		//~ for(int i=0;i<n;i++){
			//~ cout<<used[i]<<" ";
		//~ } cout<<endl;
		//~ for(int i=0;i<n;i++){
			//~ cout<<a[i]<<" ";
		//~ } cout<<endl;
		
		todo.clear();
		for(int i=0;i<n;i++){
			if(used[i]) continue;
			todo.push_back(i);
		}
		
		shuffle(todo.begin(), todo.end(), rnd);
		int half = (int)todo.size() / 2;
		if(check(half) == don) continue;
		//~ cout<<"here"<<endl;
		int l = 1, r = half;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m) > don){
				r = m;
			} else {
				l = m + 1;
			}
		} l--;
		int i = todo[l<<1], j = todo[l<<1|1];
		swap(a[i], a[j]);
		int cost = query(a);
		if(cost == n) return;
		if(cost == don + 2){
			used[i] = used[j] = 1; don += 2;
		} else {
			int p = -1;
			for(int l=0;l<n;l++){
				if(used[l] || i == l || j == l) continue;
				p = l; break;
			}
			
			assert(~p);
			swap(a[i], a[p]);
			int tmp = query(a);
			if(tmp == n) return;
			swap(a[i], a[p]);
			if(tmp < cost) used[i] = 1;
			else used[j] = 1;
			don++;
		}
	}
}

/*

8
3 6 5 7 8 1 4 2

*/

//~ signed main(){
	//~ int n; cin>>n;
	//~ B.resize(n);
	//~ for(int i=0;i<n;i++) cin>>B[i];
	//~ solve(n);
//~ }

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 17
2 Correct 0 ms 200 KB Correct! Number of queries: 9
3 Correct 1 ms 200 KB Correct! Number of queries: 24
4 Correct 1 ms 200 KB Correct! Number of queries: 33
5 Correct 1 ms 200 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 27

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 17
2 Correct 0 ms 200 KB Correct! Number of queries: 9
3 Correct 1 ms 200 KB Correct! Number of queries: 24
4 Correct 1 ms 200 KB Correct! Number of queries: 33
5 Correct 1 ms 200 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 27
7 Correct 4 ms 200 KB Correct! Number of queries: 400
8 Correct 5 ms 200 KB Correct! Number of queries: 400
9 Correct 4 ms 200 KB Correct! Number of queries: 400
10 Correct 5 ms 200 KB Correct! Number of queries: 400
11 Correct 4 ms 200 KB Correct! Number of queries: 300
12 Correct 4 ms 200 KB Correct! Number of queries: 400
13 Correct 4 ms 200 KB Correct! Number of queries: 300
14 Correct 5 ms 200 KB Correct! Number of queries: 400
15 Correct 5 ms 200 KB Correct! Number of queries: 400
16 Correct 5 ms 200 KB Correct! Number of queries: 400

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 17
2 Correct 0 ms 200 KB Correct! Number of queries: 9
3 Correct 1 ms 200 KB Correct! Number of queries: 24
4 Correct 1 ms 200 KB Correct! Number of queries: 33
5 Correct 1 ms 200 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 27
7 Correct 4 ms 200 KB Correct! Number of queries: 400
8 Correct 5 ms 200 KB Correct! Number of queries: 400
9 Correct 4 ms 200 KB Correct! Number of queries: 400
10 Correct 5 ms 200 KB Correct! Number of queries: 400
11 Correct 4 ms 200 KB Correct! Number of queries: 300
12 Correct 4 ms 200 KB Correct! Number of queries: 400
13 Correct 4 ms 200 KB Correct! Number of queries: 300
14 Correct 5 ms 200 KB Correct! Number of queries: 400
15 Correct 5 ms 200 KB Correct! Number of queries: 400
16 Correct 5 ms 200 KB Correct! Number of queries: 400
17 Correct 71 ms 200 KB Correct! Number of queries: 2400
18 Correct 58 ms 200 KB Correct! Number of queries: 2200
19 Correct 62 ms 200 KB Correct! Number of queries: 2300
20 Correct 67 ms 200 KB Correct! Number of queries: 2300
21 Correct 69 ms 200 KB Correct! Number of queries: 2300
22 Correct 65 ms 200 KB Correct! Number of queries: 2200
23 Correct 65 ms 200 KB Correct! Number of queries: 2300
24 Correct 68 ms 200 KB Correct! Number of queries: 2400
25 Correct 63 ms 200 KB Correct! Number of queries: 2300
26 Correct 71 ms 200 KB Correct! Number of queries: 2400