Japan Alumni Group Summer Camp 2013 Warming Up

Submission #828529

Source codeソースコード

#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];

ll gcd(ll a,ll b)
{
	if(a==0) return b;
	return gcd(b%a,a);
}
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(t>=2) up=false;//i>=2
			else if(t==1)
			{
				for(int j=2;j<=cnt[i];j++)
				{
					if(K%j==0)
					{
						up=false;
						break;
					}
				}
			}
		}
	}
	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);
			if(L==1)
			{
				ans[i]=i;
				continue;
			}
			int z=(int) (K%L);
			int k=0;
			while((ll) z*(ll) k%L!=1) k++;
			//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

Task問題 H - Shuffling Machine
User nameユーザ名 yutaka1999
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 2164 Byte
File nameファイル名
Exec time実行時間 73 ms
Memory usageメモリ使用量 2132 KB

Compiler messageコンパイルメッセージ

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

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 28 ms 892 KB
10 AC 27 ms 920 KB
11 AC 36 ms 1124 KB
12 AC 25 ms 800 KB
13 AC 38 ms 1136 KB
14 AC 42 ms 1264 KB
15 AC 73 ms 2132 KB
16 AC 44 ms 1260 KB
17 AC 46 ms 1252 KB
18 AC 47 ms 1260 KB
19 AC 71 ms 1904 KB
2 AC 27 ms 876 KB
20 AC 70 ms 1900 KB
21 AC 47 ms 1264 KB
22 AC 72 ms 1768 KB
23 AC 46 ms 1264 KB
24 AC 44 ms 1252 KB
25 AC 72 ms 1892 KB
26 AC 47 ms 1260 KB
27 AC 44 ms 1260 KB
28 AC 72 ms 2020 KB
29 AC 45 ms 1264 KB
3 AC 26 ms 800 KB
30 AC 46 ms 1260 KB
31 AC 72 ms 1892 KB
32 AC 45 ms 1256 KB
33 AC 46 ms 1356 KB
34 AC 48 ms 1256 KB
35 AC 28 ms 944 KB
36 AC 27 ms 880 KB
37 AC 37 ms 940 KB
38 AC 26 ms 880 KB
39 AC 27 ms 868 KB
4 AC 27 ms 924 KB
40 AC 27 ms 920 KB
41 AC 26 ms 920 KB
42 AC 25 ms 924 KB
43 AC 25 ms 872 KB
44 AC 28 ms 920 KB
45 AC 28 ms 872 KB
46 AC 27 ms 872 KB
47 AC 26 ms 924 KB
48 AC 26 ms 928 KB
5 AC 26 ms 924 KB
6 AC 24 ms 928 KB
7 AC 29 ms 872 KB
8 AC 26 ms 924 KB
9 AC 24 ms 924 KB