Submission #828515


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
#define SIZE 100005

using namespace std;
typedef long long int ll;

int to[SIZE];
bool use[SIZE];
int cnt[SIZE];
int ans[SIZE],ret[SIZE];
int nd[SIZE];

int main()
{
	int n;
	ll K;
	scanf("%d %lld",&n,&K);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&to[i]);
		to[i]--;
	}
	if(K==1)
	{
		for(int i=0;i<n;i++)
		{
			if(i!=0) printf(" ");
			printf("%d",to[i]+1);
		}puts("");
		return 0;
	}
	for(int i=0;i<n;i++)
	{
		if(!use[i])
		{
			int now=i;
			int len=0;
			do
			{
				use[now]=true;
				len++;
				now=to[now];
			}while(now!=i);
			cnt[len]++;
		}
	}
	bool up=true;
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]>0)
		{
			ll t=1,zan=K;
			int s=i;
			for(int j=2;j*j<=s;j++)
			{
				if(s%j==0)
				{
					while(s%j==0) s/=j;
					while(zan%j==0)
					{
						zan/=j;
						t*=(ll) j;
					}
				}
			}
			if(s!=1)
			{
				while(zan%s==0)
				{
					zan/=s;
					t*=(ll) s;
				}
			}
			//printf("%d %lld : %d\n",i,t,cnt[i]);
			if(cnt[i]%t!=0)
			{
				puts("Impossible");
				return 0;
			}
			if(cnt[i]>=2) up=false;
		}
	}
	if(!up)
	{
		puts("Ambiguous");
		return 0;
	}
	//全部一種類からなるcycle
	memset(use,false,sizeof(use));
	for(int i=0;i<n;i++)
	{
		if(!use[i])
		{
			int now=i;
			int L=0;
			do
			{
				use[now]=true;
				nd[L++]=now;
				now=to[now];
			}while(now!=i);
			int z=(int) (K%L);
			int k=0;
			while((ll) z*(ll) k%L!=1) k++;
			assert(k<=L);
			//ans[i]=to^k[i]=nd[pos[i]+k] -> ans[nd[i]]=nd[i+k]
			for(int j=0;j<L;j++) ans[nd[j]]=nd[(j+k)%L];
		}
	}
	//for(int i=0;i<n;i++) printf("%d ",ans[i]);puts("");
	//for(int i=0;i<n;i++) ret[ans[i]]=i;
	for(int i=0;i<n;i++)
	{
		if(i!=0) printf(" ");
		printf("%d",ans[i]+1);
	}puts("");
	return 0;
}

Submission Info

Submission Time
Task H - Shuffling Machine
User yutaka1999
Language C++ (GCC 4.4.7)
Score 0
Code Size 1919 Byte
Status WA
Exec Time 1535 ms
Memory 2032 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 36
WA × 5
TLE × 7
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 26 ms 920 KB
10 AC 24 ms 872 KB
11 AC 41 ms 1132 KB
12 AC 26 ms 924 KB
13 AC 38 ms 1132 KB
14 AC 44 ms 1256 KB
15 AC 71 ms 2032 KB
16 AC 46 ms 1256 KB
17 AC 46 ms 1256 KB
18 AC 45 ms 1264 KB
19 WA 45 ms 1264 KB
2 AC 25 ms 928 KB
20 WA 43 ms 1264 KB
21 AC 46 ms 1260 KB
22 WA 44 ms 1256 KB
23 AC 46 ms 1260 KB
24 AC 44 ms 1252 KB
25 TLE 1535 ms 2028 KB
26 AC 45 ms 1260 KB
27 AC 43 ms 1260 KB
28 WA 46 ms 1260 KB
29 AC 45 ms 1256 KB
3 AC 26 ms 796 KB
30 AC 46 ms 1260 KB
31 WA 44 ms 1348 KB
32 AC 44 ms 1260 KB
33 AC 48 ms 1256 KB
34 AC 46 ms 1256 KB
35 AC 25 ms 876 KB
36 AC 26 ms 928 KB
37 AC 26 ms 988 KB
38 AC 26 ms 924 KB
39 AC 25 ms 924 KB
4 AC 25 ms 928 KB
40 AC 25 ms 928 KB
41 AC 26 ms 928 KB
42 AC 25 ms 796 KB
43 AC 26 ms 928 KB
44 AC 26 ms 880 KB
45 TLE 1532 ms 1000 KB
46 TLE 1535 ms 1000 KB
47 TLE 1534 ms 996 KB
48 TLE 1534 ms 1008 KB
5 AC 27 ms 872 KB
6 AC 25 ms 924 KB
7 AC 32 ms 920 KB
8 TLE 1534 ms 1004 KB
9 TLE 1535 ms 1000 KB