제출 #414162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414162		errorgorn	Mouse (info1cup19_mouse)	C++17	79.39 / 100	160 ms	200 KiB

mouse

#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 / 13
• Subtask 2: 29.000004 / 38
• Subtask 3: 37.394742 / 49