QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745279 | #9432. Permutation | piggy123 | WA | 288ms | 3816kb | C++17 | 4.4kb | 2024-11-14 08:55:03 | 2024-11-14 08:55:12 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll to[1005],ans[1005],f[1005],id[1005],vis[1005],n;
vector<ll> pp[1005];
mt19937 mt(time(0));
ll find(ll a){
if(f[a]!=a)f[a]=find(f[a]);
return f[a];
}
void merge(ll a,ll b){
ll x=find(a),y=find(b);
if (x==y)return;
if (pp[x].size()>pp[y].size())swap(x,y);
f[x]=y;
for (ll i:pp[x])pp[y].push_back(i);
}
void solve(ll l,ll r,vector<ll>&all){
// cout<<l<<","<<r<<":";
// for (ll i:all)cout<<i<< ",";
// cout<< endl;
if (l==r){
ans[l]=all[0];
return;
}
vector<ll> cs;
vector<ll> pl,pr;
for (ll i=0;i<all.size();i++)pp[i+1].clear(),pp[i+1].push_back(i+1),cs.push_back(i+1),id[all[i]]=i+1,to[i+1]=all[i],f[i+1]=i+1,vis[all[i]]=1;
ll non=0;
for (ll i=1;i<=n;i++)if (vis[i])non=i;
for (ll i=0;i<all.size();i++)vis[all[i]]=0;
ll mid=(l+r)>>1;
while (cs.size()>1){
// cout<<"? ";
// for (ll i:cs)cout<<i<<" ";
// cout<< endl;
ll p1=cs[mt()%cs.size()],p2=cs[mt()%cs.size()];
while (p1==p2)p2=cs[mt()%cs.size()];
cout<<"0 ";
for (ll i=1;i<l;i++)cout<<non<<" ";
for (ll i=l;i<=mid;i++)cout<<to[find(p1)]<<" ";
for (ll i=mid+1;i<=r;i++)cout<<to[find(p2)]<<" ";
for (ll i=r+1;i<=n;i++)cout<<non<<" ";
cout<< endl;
ll x;
cin >> x;
if (x==0){
cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
for (ll i:pp[find(p2)])pl.push_back(to[i]);
for (ll i:pp[find(p1)])pr.push_back(to[i]);
}else if (x==2){
cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
for (ll i:pp[find(p1)])pl.push_back(to[i]);
for (ll i:pp[find(p2)])pr.push_back(to[i]);
}else{
merge(p1,p2);
cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
cs.push_back(find(p1));
}
}
if (cs.size()==1){
if (pl.size()!=mid-l+1)pl.push_back(to[cs[0]]);
if (pr.size()!=r-mid)pr.push_back(to[cs[0]]);
}
solve(l,mid,pl);
solve(mid+1,r,pr);
}
int main(){
cin >> n;
vector<ll> all;
for (ll i=1;i<=n;i++)all.push_back(i);
solve(1,n,all);
cout<< "1 ";
for (ll i=1;i<=n;i++){
cout<< ans[i]<<" ";
}
return 0;
}
/*
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
input:
5 2 0 2 0 2
output:
0 2 2 2 1 1 0 5 5 5 3 3 0 3 3 2 4 4 0 4 3 4 4 4 0 5 5 5 1 5 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Wrong Answer
time: 288ms
memory: 3816kb
input:
1000 0 0 1 2 0 1 1 2 0 1 2 1 2 1 1 1 0 0 1 1 2 1 1 1 1 2 0 2 1 1 2 1 1 1 1 2 1 1 0 1 0 1 1 1 1 1 2 0 1 2 2 0 0 1 2 1 1 0 2 1 0 1 0 1 2 2 1 1 0 2 2 0 0 0 1 2 2 1 0 0 1 1 2 1 1 1 2 0 1 2 2 1 2 2 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 2 1 0 2 2 1 0 1 1 1 0 1 0 1 2 1 2 1 2 0 1 0 1 1 0 1 1 2 1 1 0 1 1 1 1 0 1 0 0...
output:
0 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 6...
result:
wrong answer Wrong Anser