ABC371G 求调
  • 板块学术版
  • 楼主nr0728
  • 当前回复12
  • 已保存回复13
  • 发布时间2024/9/14 21:44
  • 上次更新2024/9/23 15:59:01
查看原帖
ABC371G 求调
682739
nr0728楼主2024/9/14 21:44
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,ubuf[1<<23];
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
	TP x=0;
	int f=0;
	char ch=getchar();
	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
	(read(args),...);
}
template<typename TP> inline void write(TP x)
{
	(x<0)?(putchar('-'),x=-x):0;
	(x>9)?(write(x/10),0):0;
	putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
write<TP>(x);
	puts("");
}
int n,p[200001],a[200001],vis[200001],ans[200001];
signed main()
{
	read(n);
	rep(i,1,n) read(p[i]);
	rep(i,1,n) read(a[i]);
	rep(i,1,n) if(!vis[i])
	{
		vector<int> ret;
		int x=i;
		while(!vis[x])
		{
			vis[x]=1;
			ret.emplace_back(x);
			x=p[x];
		}
		vector<int> val(ret.size());
		rep(j,0,ret.size()-1) val[j]=a[ret[j]];
		int pi=0,pj=1,offset=0,n=val.size();
		while(pi<n&&pj<n&&offset<n)
		{
			int px=val[(pi+offset)%n],py=val[(pj+offset)%n];
			if(px==py) {++offset;continue;}
			if(px>py) pi+=offset+1;
			else pj+=offset+1;
			if(pi==pj) ++pi;
			offset=0;
		}
		rep(j,0,n-1) ans[ret[j]]=val[(min(pi,pj)+j)%n];
	}
	rep(i,1,n) write(ans[i]),putchar(' ');
	return 0;
}
2024/9/14 21:44
加载中...