QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745279#9432. Permutationpiggy123WA 288ms3816kbC++174.4kb2024-11-14 08:55:032024-11-14 08:55:12

Judging History

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

  • [2024-11-14 08:55:12]
  • 评测
  • 测评结果:WA
  • 用时:288ms
  • 内存:3816kb
  • [2024-11-14 08:55:03]
  • 提交

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;
}

/*
                                                                
 ■■■■■     ■■      ■■■     ■■■   ■    ■     ■     ■■■■    ■■■■  
 ■   ■■    ■■     ■  ■■   ■  ■■  ■    ■    ■■     ■  ■■  ■■  ■  
 ■    ■    ■■    ■    ■  ■    ■   ■  ■    ■■■    ■■  ■■  ■   ■■ 
 ■    ■    ■■    ■    ■  ■    ■   ■  ■     ■■    ■   ■■      ■■ 
 ■    ■    ■■    ■       ■         ■■      ■■        ■■      ■  
 ■   ■■    ■■    ■  ■■■  ■  ■■■    ■■      ■■       ■■     ■■■  
 ■■■■■     ■■    ■    ■  ■    ■    ■■      ■■      ■■        ■■ 
 ■         ■■    ■    ■  ■    ■    ■■      ■■     ■■          ■ 
 ■         ■■    ■    ■  ■    ■    ■■      ■■     ■      ■   ■■ 
 ■         ■■    ■■  ■■  ■■  ■■    ■■      ■■    ■       ■■  ■■ 
 ■         ■■      ■■■■    ■■■■    ■■      ■■    ■■■■■■   ■■■■  
*/

详细

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