Submission #101994

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define foreach(it,X) for(__typeof(X.begin()) it=X.begin();it!=X.end();it++)
#define fir first
#define sec second
//#define foreachM(it,X) for(map<int,int>::iterator it=X.begin();it!=X.end();it++)
#define vi vector<int>
#define pb push_back
#define sz(x) ((int)(x).size())

typedef long long ll;

ll N,K,b[100010];
int used[100010];
map<int,int> M;
set<int> P;
map<int,int> K2;
map<int,ll> K3;
vector<vector<int> > seq;
int ans[100010];

int main(){
	cin>>N>>K;
	rep(i,N)cin>>b[i],b[i]--;
	rep(i,N)if(!used[i]){
		int cur=i;
		int len=0;
		vi v;
		while(!used[cur]){
			used[cur]=1;
			v.pb(cur);
			len++;
			cur=b[cur];
		}
		M[len]++;
		seq.pb(v);
	}
	foreach(it,M){
		int L=it->fir;
		for(int i=2;i*i<=L;i++)if(L%i==0){
			P.insert(i);
			while(L%i==0)L/=i;
		}
		if(L>1)P.insert(L);
	}
	foreach(it,P){
		ll x=K;
		K3[*it]=1;
		while(x%(*it)==0){
			K2[*it]++;
			K3[*it]*=*it;
			x/=*it;
		}
	}
	int combine=0;
	foreach(it,M){
		ll len=it->fir,num=it->sec;
		foreach(it2,P){
			ll p=*it2;
			if(len % p == 0){
				if(num % K3[p] != 0){
					return cout<<"Impossible"<<endl,0;
				}
				if(K3[p] != 1) combine=1;
			}
		}
	}
	if(combine)return cout<<"Ambiguous"<<endl,0;
	
	if(/*sz(K2)!=0*/K>=2){
		ll minP = -1;//= K2.begin() -> fir;
		for(int i=2;i<100005;i++)if(K % i == 0){
			minP = i;
			break;
		}
		if(minP == -1)goto end;
		foreach(it,M){
			ll num=it->sec;
			if(num >= minP)return cout<<"Ambiguous"<<endl,0;
		}
	}
	end:;
	
	foreach(it,seq){
		vi v=*it;
		vi w(sz(v));
		ll cur=0;
		rep(i,sz(v)){
			w[cur] = v[i];
			cur += K;
			cur %= sz(v);
		}
		rep(i,sz(w)){
			if(i<sz(w)-1) ans[w[i]] = w[i+1];
			else ans[w[i]] = w[0];
		}
	}
	
	rep(i,N)cout<<ans[i]+1<<(i==N-1 ? "\n":" ");
}

Submission Info

Judge Result