QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#745258#9432. Permutationpiggy123WA 1ms3708kbC++174.2kb2024-11-14 08:46:322024-11-14 08:46:37

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 08:46:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3708kb
  • [2024-11-14 08:46:32]
  • 提交

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){
	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){
		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));
		}
	}
	if (cs.size()==1){
		if (pl.size()!=mid-l+1)pl.push_back(cs[0]);
		if (pr.size()!=r-mid)pr.push_back(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: 0
Wrong Answer
time: 1ms
memory: 3708kb

input:

5
2
0
3
1
3

output:

0 2 2 2 5 5 
0 1 1 1 3 3 
0 4 4 2 5 5 
0 2 2 3 5 5 
0 4 4 4 1 5 
1 1 1 2 1 1 

result:

wrong answer Wrong Anser