| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 422111 | CSQ31 | Mouse (info1cup19_mouse) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "permutation.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef vector<vector<ll>> VII;
typedef pair<int,int> pii;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>a;
vector<bool>unsolved;
vector<pii>swaps;
vector<pii>partition(){
vector<int>s;
for(int i=0;i<sz(unsolved);i++){
if(!unsolved[i])s.pb(i);
}
shuffle(all(s),rng);
vector<pii>res;
for(int i=1;i<sz(s);i+=2)res.pb({s[i],s[i-1]});
return res;
}
void swap_array(int l,int r){
for(int i=l;i<=r;i++)swap(a[swaps[i].fi],a[swaps[i].se]);
}
void solve(int n){
for(int i=1;i<=n;i++)a.pb(i);
while(true){
shuffle(all(a),rng);
int res = query(a);
if(res == n)return;
if(!res)break;
}
//cout<<"derangement"<<'\n';
//for(int x:a)cout<<x<<" ";
//cout<<'\n';
unsolved.assign(n,0); //what indexes have we solved
int solved = 0;
int cnt = 0;
while(true){
int cur=0;
//for(int i=0;i<n;i++)cout<<a[i]<<" ";
//cout<<'\n';
//for(int i=0;i<n;i++)cout<<unsolved[i]<<" ";
//cout<<'\n';
while(true){ //random until find one that increases answer
swaps = partition();
swap_array(0,sz(swaps)-1);
cur = query(a);
swap_array(0,sz(swaps)-1);
if(cur == n)return;
if(cur > solved)break;
cnt++;
}
swap_array(0,sz(swaps)-1);
int l = 0,r = sz(swaps)-1;
int res = 0;
while(r>l){
int mid = (l+r)/2;
swap_array(l,mid);
res = query(a);
swap_array(l,mid);
if(res == n)return;
if(res < cur)r = mid;
else l = mid+1;
}
swap_array(0,sz(swaps)-1);
swap_array(l,l);
res = query(a);
swap_array(l,l);
//cout<<"thonk2"<<'\n';
//for(int i=0;i<n;i++)cout<<a[i]<<" ";
//cout<<'\n';
if(res == solved+2){ //both are correct
//cout<<"CASE 1:"<<swaps[l].fi<<" "<<swaps[l].se<<'\n';
swap_array(l,l);
unsolved[swaps[l].fi] = 1;
unsolved[swaps[l].se] = 1;
solved+=2;
}else{//res == cur-1;
//we have indexes a,b -> b,a
//WLOG b is correct
//case 1 : swap smtg with b if answer = solved,b is correct
//case 2 : swap smtg with a
//subcase 1:answer = solved+1,b is correct /the other index apart from our choice
//subcase 2:answer = solved+2,b is correct
//subcase 3:answer = solved+3,b c a is correct we solved three indexes
int x = swaps[l].fi;
int y = swaps[l].se;
int z = -1;
for(int i=0;i<n;i++){if(!unsolved[i] && i != x && i!=y){z=i;break;}}
swap(a[x],a[y]); // z,x,y
swap(a[x],a[z]); //we have x,y -> y,x -> y,z,x
res = query(a);
//cout<<x<<" "<<y<<" "<<z<<'\n';
//cout<<solved<<" "<<res<<'\n';
//for(int i=0;i<n;i++)cout<<a[i]<<" ";
//cout<<'\n';
if(res == n)return;
if(res == solved){//index x is correct
// cout<<"CASE 2"<<'\n';
swap(a[x],a[z]);
solved++;
unsolved[x] = 1;
}else if(res <= solved+2){//index y is correct
//cout<<"CASE 3"<<'\n';
swap(a[x],a[z]);
solved++;
unsolved[y] = 1;
}else{
//cout<<"CASE 4"<<'\n';
solved+=3;
unsolved[x] = unsolved[y] = unsolved[z] = 1;
}
}
}
}