Submission #57785244

---

Source Code Expand

#include<stdio.h>
#include<vector>
using namespace std;
const int N=200005;

#define ll __int128

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

ll gcd(ll x,ll y){
	if(y) return gcd(y,x%y);
	else return x;
}

struct equ{
	ll r,m;
};

equ merge(equ X,equ Y){
	if(!X.m) return Y;
	if(!Y.m) return X;
	
	ll a=X.m,b=Y.m,c=Y.r-X.r,x,y;
	ll d=exgcd(a,b,x,y);
	
	if(c%d) return (equ){0,0};
	
	a/=d,b/=d,c/=d;
	x=((x*c)%b+b)%b;
	
	Y.m=X.m/gcd(X.m,Y.m)*Y.m;
	Y.r=((x*X.m%Y.m+X.r)%Y.m+Y.m)%Y.m;
	return Y;
}

int n;
int p[N],a[N],b[N];
vector<int> e[N],g;
equ now,tmp;
bool vis[N];

void dfs(int x){
	g.push_back(x);
	vis[x]=true;
	
	for(int v:e[x])
	if(!vis[v]) dfs(v);
}

signed main(){
	int i,j,k;
	scanf("%d",&n);
	
	for(i=1;i<=n;i++){
		scanf("%d",&p[i]);
		e[i].push_back(p[i]);
	}for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	for(i=1;i<=n;i++) if(!vis[i]){
		g.clear();
		dfs(i);
		k=-1;
		
		for(j=0;j<g.size();j++)
		if(merge(now,(equ){(ll)j,(ll)g.size()}).m
		&&(k<0||a[g[j]]<a[g[k]])) k=j;
		
		if(k<0) return 114;
		
		now=merge(now,(equ){(ll)k,(ll)g.size()});
		
		for(j=0;j<g.size();j++)
			b[g[j]]=a[g[(j+k)%g.size()]];
	}
	
	for(i=1;i<=n;i++)
		printf("%d ",b[i]);
	
	puts("");
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:74:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   74 |                 for(j=0;j<g.size();j++)
      |                         ~^~~~~~~~~
Main.cpp:82:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   82 |                 for(j=0;j<g.size();j++)
      |                         ~^~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:64:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |                 scanf("%d",&p[i]);
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp:67:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~

Judge Result