oj.uz

Submission #414162

# Submission time Handle Problem Language Result Execution time Memory
414162 2021-05-30T07:23:03 Z errorgorn Mouse (info1cup19_mouse) C++17
79.3947 / 100
 160 ms 200 KB 
#include "grader.h"

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

#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(342759);

int n;
vector<int> ans;
vector<int> pos; //which pos idk

void shuf(){
	rep(x,0,sz(pos)){
		swap(ans[pos[x]],ans[pos[rng()%(x+1)]]);
	}
}

void solve(int N) {
	n=N;
	
	rep(x,1,n+1) ans.pub(x);
	rep(x,0,n) pos.pub(x);
	
	int correct=0;
	
	while (true){
		int curr;
		do{
			shuf();
			curr=query(ans);
			if (curr==n) return;
		} while (curr!=correct);
		
		vector<int> idx;
		for (int x=0;x<sz(pos)-1;x+=2) idx.pub(x);
		
		for (auto &it:idx) swap(ans[pos[it]],ans[pos[it+1]]);
		
		curr=query(ans);
		if (curr==n) return;
		if (query(ans)==correct) continue;
		
		for (auto &it:idx) swap(ans[pos[it]],ans[pos[it+1]]);
		
		while (sz(idx)!=1){
			int temp=sz(idx)/2;
			rep(x,0,temp) swap(ans[pos[idx[x]]],ans[pos[idx[x]+1]]);
			
			curr=query(ans);
			if (curr==n) return;
			
			bool left=true;
			if (curr==correct) left=false;
			
			rep(x,0,temp) swap(ans[pos[idx[x]]],ans[pos[idx[x]+1]]);
			
			vector<int> idx2;
			if (left) rep(x,0,temp) idx2.pub(idx[x]);
			else rep(x,temp,sz(idx)) idx2.pub(idx[x]);
			swap(idx,idx2);
		}
		
		swap(ans[pos[idx[0]]],ans[pos[idx[0]+1]]);
		curr=query(ans);
		if (curr==n) return;
		
		if (curr==correct+2){
			pos.erase(pos.begin()+idx[0]);
			pos.erase(pos.begin()+idx[0]);
			
			correct+=2;
		}
		else{
			int temp;
			if (idx[0]==0) temp=pos.back();
			else temp=pos.front();
			
			swap(ans[pos[idx[0]]],ans[temp]);
			curr=query(ans);
			if (curr==n) return;
			swap(ans[pos[idx[0]]],ans[temp]);
			
			if (curr==correct){
				pos.erase(pos.begin()+idx[0]);
			}
			else{
				pos.erase(pos.begin()+idx[0]+1);
			}
			
			correct++;
		}
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 43
2 Correct 1 ms 200 KB Correct! Number of queries: 11
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 2 ms 200 KB Correct! Number of queries: 34
5 Correct 1 ms 200 KB Correct! Number of queries: 33
6 Correct 1 ms 200 KB Correct! Number of queries: 24

Subtask #2
29.000004 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 43
2 Correct 1 ms 200 KB Correct! Number of queries: 11
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 2 ms 200 KB Correct! Number of queries: 34
5 Correct 1 ms 200 KB Correct! Number of queries: 33
6 Correct 1 ms 200 KB Correct! Number of queries: 24
7 Correct 11 ms 200 KB Correct! Number of queries: 600
8 Correct 11 ms 200 KB Correct! Number of queries: 600
9 Correct 8 ms 200 KB Correct! Number of queries: 500
10 Correct 8 ms 200 KB Correct! Number of queries: 600
11 Correct 9 ms 200 KB Correct! Number of queries: 500
12 Correct 10 ms 200 KB Correct! Number of queries: 600
13 Correct 10 ms 200 KB Correct! Number of queries: 600
14 Correct 12 ms 200 KB Correct! Number of queries: 700
15 Correct 12 ms 200 KB Correct! Number of queries: 600
16 Correct 12 ms 200 KB Correct! Number of queries: 600

Subtask #3
37.394742 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 43
2 Correct 1 ms 200 KB Correct! Number of queries: 11
3 Correct 1 ms 200 KB Correct! Number of queries: 18
4 Correct 2 ms 200 KB Correct! Number of queries: 34
5 Correct 1 ms 200 KB Correct! Number of queries: 33
6 Correct 1 ms 200 KB Correct! Number of queries: 24
7 Correct 11 ms 200 KB Correct! Number of queries: 600
8 Correct 11 ms 200 KB Correct! Number of queries: 600
9 Correct 8 ms 200 KB Correct! Number of queries: 500
10 Correct 8 ms 200 KB Correct! Number of queries: 600
11 Correct 9 ms 200 KB Correct! Number of queries: 500
12 Correct 10 ms 200 KB Correct! Number of queries: 600
13 Correct 10 ms 200 KB Correct! Number of queries: 600
14 Correct 12 ms 200 KB Correct! Number of queries: 700
15 Correct 12 ms 200 KB Correct! Number of queries: 600
16 Correct 12 ms 200 KB Correct! Number of queries: 600
17 Correct 157 ms 200 KB Correct! Number of queries: 3900
18 Correct 128 ms 200 KB Correct! Number of queries: 3700
19 Correct 138 ms 200 KB Correct! Number of queries: 3600
20 Correct 148 ms 200 KB Correct! Number of queries: 3600
21 Correct 138 ms 200 KB Correct! Number of queries: 3700
22 Correct 139 ms 200 KB Correct! Number of queries: 3600
23 Correct 148 ms 200 KB Correct! Number of queries: 3800
24 Correct 160 ms 200 KB Correct! Number of queries: 3900
25 Correct 141 ms 200 KB Correct! Number of queries: 3800
26 Correct 156 ms 200 KB Correct! Number of queries: 3800