oj.uz

Submission #413766

# Submission time Handle Problem Language Result Execution time Memory
413766 2021-05-29T11:51:22 Z oolimry Mouse (info1cup19_mouse) C++17
100 / 100
 106 ms 296 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 18
2 Correct 1 ms 200 KB Correct! Number of queries: 16
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 17
5 Correct 1 ms 200 KB Correct! Number of queries: 22
6 Correct 1 ms 200 KB Correct! Number of queries: 28

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 18
2 Correct 1 ms 200 KB Correct! Number of queries: 16
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 17
5 Correct 1 ms 200 KB Correct! Number of queries: 22
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 7 ms 200 KB Correct! Number of queries: 400
8 Correct 7 ms 200 KB Correct! Number of queries: 400
9 Correct 7 ms 200 KB Correct! Number of queries: 300
10 Correct 8 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 7 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 400
15 Correct 5 ms 200 KB Correct! Number of queries: 400
16 Correct 6 ms 200 KB Correct! Number of queries: 400

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 18
2 Correct 1 ms 200 KB Correct! Number of queries: 16
3 Correct 1 ms 200 KB Correct! Number of queries: 21
4 Correct 1 ms 200 KB Correct! Number of queries: 17
5 Correct 1 ms 200 KB Correct! Number of queries: 22
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 7 ms 200 KB Correct! Number of queries: 400
8 Correct 7 ms 200 KB Correct! Number of queries: 400
9 Correct 7 ms 200 KB Correct! Number of queries: 300
10 Correct 8 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 7 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 400
15 Correct 5 ms 200 KB Correct! Number of queries: 400
16 Correct 6 ms 200 KB Correct! Number of queries: 400
17 Correct 102 ms 200 KB Correct! Number of queries: 2400
18 Correct 89 ms 200 KB Correct! Number of queries: 2300
19 Correct 92 ms 200 KB Correct! Number of queries: 2300
20 Correct 90 ms 200 KB Correct! Number of queries: 2300
21 Correct 87 ms 296 KB Correct! Number of queries: 2300
22 Correct 91 ms 200 KB Correct! Number of queries: 2200
23 Correct 91 ms 200 KB Correct! Number of queries: 2300
24 Correct 106 ms 200 KB Correct! Number of queries: 2400
25 Correct 89 ms 200 KB Correct! Number of queries: 2400
26 Correct 104 ms 200 KB Correct! Number of queries: 2400