#include <bits/stdc++.h>
#ifndef LOCAL
#include <grader.h>
#endif
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
#ifdef LOCAL
vector<int>ans;
int sz;
bool good=0;
int query(vector<int> v){
if(good)assert(0);
int res=0;
for(int i=1;i<=sz;i++){
res+=v[i]==ans[i];
}
if(res==sz)good=1;
return res;
}
#endif
int S;
vector<int>out;
vector<int>aval;
void get(deque<int> vec){ // vec->numbers whose index we still dk
// try to find the real index of the first guy
for(auto it=vec.begin();it!=vec.end();){
if(out[*it]!=-1){
it=vec.erase(it);
} else{
++it;
}
}
if(vec.empty())return;
vector<int> lftidxes;
vector<int> qq(S+1);
for(int i=1;i<=S;i++){
if(aval[i]==-1)lftidxes.push_back(i);
else qq[i]=aval[i];
}
//cerr<<lftidxes.size()<<endl;
//cerr<<"lft:";
//for(auto x:lftidxes)cout<<x<<" ";
//cerr<<endl;
for(int i=0;i<(int)vec.size();i++){
qq[lftidxes[i]]=vec[i];
}
int oval=query(qq);
if(oval==S)return;
vector<int> cands;
for(int i=1;i<(int)vec.size();i++){
swap(qq[lftidxes[0]],qq[lftidxes[i]]);
int qval=query(qq);
if(qval==S)return;
swap(qq[lftidxes[0]],qq[lftidxes[i]]);
if(qval==oval+2){
out[vec[0]]=lftidxes[i];
aval[lftidxes[i]]=vec[0];
out[vec[i]]=lftidxes[0];
aval[lftidxes[0]]=vec[i];
get(vec);
return;
} else if(qval==oval+1){
cands.push_back(i);
}
}
if(cands.empty()){ // this means that the vec[0]'s real index is just lftidx[0]
out[vec[0]]=lftidxes[0];
aval[lftidxes[0]]=vec[0];
get(vec);
return;
}
if(cands.size() == 1){
assert(0);
}
if(cands.size() == 2){
int i0=lftidxes[0];
int i1=lftidxes[cands[0]];
int i2=lftidxes[cands[1]];
int v0=vec[0];
int v1=vec[cands[0]];
int v2=vec[cands[1]];
qq[i2]=v0;
qq[i1]=v2;
qq[i0]=v1;
int qval=query(qq);
if(qval==S)return;
if(qval>=oval+2){
aval[i2]=v0;
aval[i0]=v1;
out[v0]=i2;
out[v1]=i0;
get(vec);
return;
} else{
aval[i1]=v0;
aval[i0]=v2;
out[v0]=i1;
out[v2]=i0;
get(vec);
return;
}
}
assert(0);
}
void solve(int n){
S=n;
// let's just try to solve index by index first
out=vector<int>(S+1,-1);//what is the index of the value
aval=vector<int>(S+1,-1);//what is the value of the index
deque<int> vec;
for(int i=1;i<=S;i++){
vec.push_back(i);
}
get(vec);
}
#ifdef LOCAL
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>sz;
ans=vector<int>(sz+1);
for(int i=1;i<=sz;i++){
cin>>ans[i];
}
solve(sz);
cout<<good<<endl;
}
#endif
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
