oj.uz

Submission #414281

# Submission time Handle Problem Language Result Execution time Memory
414281 2021-05-30T09:51:13 Z errorgorn Mouse (info1cup19_mouse) C++17
100 / 100
 79 ms 304 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

#define vi pair<vector<int>,int>

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

const int LIM=2;

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;
	
	int curr;
	
	do{
		shuf();
		curr=query(ans);
		num++;
		if (curr==n) return;
	} while (curr);
	
	while (true){
		vector<int> idx;
		int avail;
		
		assert(correct==query(ans));
		
		do{
			rep(x,0,sz(pos)) swap(pos[x],pos[rng()%(x+1)]);
			
			idx.clear();
			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;
			avail=curr-correct;
			
			for (auto &it:idx) swap(ans[pos[it]],ans[pos[it+1]]);
		} while ((avail<LIM && n-correct>5) || avail==0);
		
		//cout<<"avail: "<<avail<<endl;
		
		set<int> bad;
		vector<vi> store={vi(idx,avail)};
		
		while (avail){
			idx=store.back().fi;
			int nc=store.back().se+correct;
			//cout<<"idx: "; for (auto &it:idx) cout<<it<<" "; cout<<endl;
			//cout<<"nc: "<<nc<<endl;
			store.pob();
			
			
			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;
				
				rep(x,0,temp) swap(ans[pos[idx[x]]],ans[pos[idx[x]+1]]);
				
				vector<int> idxl,idxr;
				rep(x,0,temp) idxl.pub(idx[x]);
				rep(x,temp,sz(idx)) idxr.pub(idx[x]);
				
				if (curr!=correct){
					if (nc!=curr) store.pub(vi(idxr,nc-curr));
					idx=idxl;
					nc=curr;
				}
				else{
					idx=idxr;
					nc=nc-(curr-correct);
				}
			}
			
			swap(ans[pos[idx[0]]],ans[pos[idx[0]+1]]);
			//cout<<"swap: "<<pos[idx[0]]<<" "<<pos[idx[0]+1]<<endl;
			curr=nc;
			
			if (curr==correct+2){
				bad.insert(pos[idx[0]]);
				bad.insert(pos[idx[0]+1]);
				
				correct+=2;
				avail-=2;
			}
			else{
				int temp;
				for (auto &it:pos){
					if (it!=pos[idx[0]] && it!=pos[idx[0]+1]
						&& !bad.count(it)){
						
						temp=it;
						break;
					}
				}
				//cout<<"temp: "<<temp<<endl;
				
				swap(ans[pos[idx[0]]],ans[temp]);
				curr=query(ans);
				if (curr==n) return;
				swap(ans[pos[idx[0]]],ans[temp]);
				
				if (curr==correct){
					bad.insert(pos[idx[0]]);
				}
				else{
					bad.insert(pos[idx[0]+1]);
				}
				
				correct++;
				avail--;
			}
		}
		
		vector<int> npos;
		for (auto &it:pos) if (!bad.count(it)) npos.pub(it);
		swap(pos,npos);
		
		//cout<<"num left: "<<sz(pos)<<endl;
		
		//for (auto &it:ans) cout<<it<<" "; cout<<endl;
		//cout<<endl;
		//for (auto &it:pos) cout<<it<<" "; cout<<endl;
		//cout<<endl;
	}
}

Compilation message

mouse.cpp: In function 'void solve(int)':
mouse.cpp:137:35: warning: 'temp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |     swap(ans[pos[idx[0]]],ans[temp]);
      |                                   ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 18
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: 27
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 21

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 18
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: 27
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 21
7 Correct 5 ms 296 KB Correct! Number of queries: 300
8 Correct 6 ms 200 KB Correct! Number of queries: 300
9 Correct 5 ms 200 KB Correct! Number of queries: 300
10 Correct 3 ms 292 KB Correct! Number of queries: 300
11 Correct 4 ms 200 KB Correct! Number of queries: 300
12 Correct 5 ms 200 KB Correct! Number of queries: 300
13 Correct 5 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 300
15 Correct 6 ms 200 KB Correct! Number of queries: 300
16 Correct 6 ms 200 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 18
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: 27
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 21
7 Correct 5 ms 296 KB Correct! Number of queries: 300
8 Correct 6 ms 200 KB Correct! Number of queries: 300
9 Correct 5 ms 200 KB Correct! Number of queries: 300
10 Correct 3 ms 292 KB Correct! Number of queries: 300
11 Correct 4 ms 200 KB Correct! Number of queries: 300
12 Correct 5 ms 200 KB Correct! Number of queries: 300
13 Correct 5 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 300
15 Correct 6 ms 200 KB Correct! Number of queries: 300
16 Correct 6 ms 200 KB Correct! Number of queries: 300
17 Correct 79 ms 284 KB Correct! Number of queries: 2000
18 Correct 66 ms 200 KB Correct! Number of queries: 1800
19 Correct 73 ms 200 KB Correct! Number of queries: 1800
20 Correct 78 ms 200 KB Correct! Number of queries: 2000
21 Correct 77 ms 296 KB Correct! Number of queries: 1900
22 Correct 67 ms 288 KB Correct! Number of queries: 1900
23 Correct 74 ms 304 KB Correct! Number of queries: 1800
24 Correct 71 ms 304 KB Correct! Number of queries: 1900
25 Correct 79 ms 284 KB Correct! Number of queries: 1900
26 Correct 72 ms 288 KB Correct! Number of queries: 2000