oj.uz

Submission #414171

# Submission time Handle Problem Language Result Execution time Memory
414171 2021-05-30T08:05:52 Z errorgorn Mouse (info1cup19_mouse) C++17
92.3846 / 100
 130 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;
	int num=0;
	
	while (true){
		int curr;
		
		do{
			shuf();
			curr=query(ans);
			num++;
			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;
		int avail=curr-correct;
		
		for (auto &it:idx) swap(ans[pos[it]],ans[pos[it+1]]);
		
		vector<int> npos;
		while (avail){
			idx.clear();
			for (int x=0;x<sz(pos)-1;x+=2) idx.pub(x);
			
			int nc=correct+avail;
			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]);
					nc=curr;
				}
				else{
					rep(x,temp,sz(idx)) idx2.pub(idx[x]);
					nc=nc-(curr-correct);
				}
				swap(idx,idx2);
			}
			
			swap(ans[pos[idx[0]]],ans[pos[idx[0]+1]]);
			curr=nc;
			
			if (curr==correct+2){
				correct+=2;
				avail-=2;
			}
			else{
				int temp;
				if (!npos.empty()) temp=npos.front();
				else 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){
					npos.pub(pos[idx[0]+1]);
				}
				else{
					npos.pub(pos[idx[0]]);
				}
				
				correct++;
				avail--;
			}
			
			pos.erase(pos.begin()+idx[0]);
			pos.erase(pos.begin()+idx[0]);
		}
		
		for (auto &it:npos) pos.pub(it);
		
		//cout<<"derangement time: "<<num<<endl;
		//cout<<"num left: "<<sz(pos)<<endl;
		
		//for (auto &it:ans) cout<<it<<" "; cout<<endl;
		//for (auto &it:pos) cout<<it<<" "; cout<<endl;
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 20
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 15
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 19

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 20
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 15
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 19
7 Correct 8 ms 200 KB Correct! Number of queries: 500
8 Correct 8 ms 200 KB Correct! Number of queries: 500
9 Correct 9 ms 200 KB Correct! Number of queries: 500
10 Correct 9 ms 200 KB Correct! Number of queries: 500
11 Correct 6 ms 200 KB Correct! Number of queries: 400
12 Correct 8 ms 200 KB Correct! Number of queries: 500
13 Correct 5 ms 200 KB Correct! Number of queries: 400
14 Correct 9 ms 200 KB Correct! Number of queries: 500
15 Correct 6 ms 200 KB Correct! Number of queries: 400
16 Correct 7 ms 200 KB Correct! Number of queries: 500

Subtask #3
44.384592 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 20
2 Correct 1 ms 200 KB Correct! Number of queries: 7
3 Correct 1 ms 200 KB Correct! Number of queries: 15
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 200 KB Correct! Number of queries: 19
7 Correct 8 ms 200 KB Correct! Number of queries: 500
8 Correct 8 ms 200 KB Correct! Number of queries: 500
9 Correct 9 ms 200 KB Correct! Number of queries: 500
10 Correct 9 ms 200 KB Correct! Number of queries: 500
11 Correct 6 ms 200 KB Correct! Number of queries: 400
12 Correct 8 ms 200 KB Correct! Number of queries: 500
13 Correct 5 ms 200 KB Correct! Number of queries: 400
14 Correct 9 ms 200 KB Correct! Number of queries: 500
15 Correct 6 ms 200 KB Correct! Number of queries: 400
16 Correct 7 ms 200 KB Correct! Number of queries: 500
17 Correct 130 ms 200 KB Correct! Number of queries: 2800
18 Correct 92 ms 200 KB Correct! Number of queries: 2800
19 Correct 96 ms 200 KB Correct! Number of queries: 2600
20 Correct 130 ms 200 KB Correct! Number of queries: 2800
21 Correct 108 ms 200 KB Correct! Number of queries: 2800
22 Correct 107 ms 200 KB Correct! Number of queries: 2700
23 Correct 111 ms 200 KB Correct! Number of queries: 2900
24 Correct 117 ms 200 KB Correct! Number of queries: 2800
25 Correct 116 ms 200 KB Correct! Number of queries: 2800
26 Correct 104 ms 200 KB Correct! Number of queries: 3000