Japan Alumni Group Summer Camp 2013 Warming Up

Submission #828501

Source codeソースコード

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#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]--;
	}
	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<=s;j++)
			{
				if(s%j==0)
				{
					while(s%j==0) s/=j;
					while(zan%j==0)
					{
						zan/=j;
						t*=(ll) j;
					}
				}
			}
			//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;
				L++;
				now=to[now];
			}while(now!=i);
			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状態 WA
Score得点 0
Source lengthソースコード長 1669 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:24: 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 0 / 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 26 ms 808 KB
10 AC 26 ms 796 KB
11 AC 40 ms 1060 KB
12 AC 25 ms 668 KB
13 AC 38 ms 1060 KB
14 AC 45 ms 1180 KB
15 AC 69 ms 1952 KB
16 AC 45 ms 1184 KB
17 AC 48 ms 1184 KB
18 AC 46 ms 1184 KB
19 WA
2 AC 26 ms 800 KB
20 WA
21 AC 47 ms 1188 KB
22 WA
23 AC 46 ms 1192 KB
24 AC 46 ms 1184 KB
25 TLE
26 AC 45 ms 1184 KB
27 AC 46 ms 1192 KB
28 WA
29 AC 45 ms 1184 KB
3 TLE
30 AC 47 ms 1180 KB
31 WA
32 AC 46 ms 1188 KB
33 AC 45 ms 1192 KB
34 AC 46 ms 1180 KB
35 AC 26 ms 804 KB
36 AC 23 ms 804 KB
37 AC 27 ms 924 KB
38 AC 26 ms 800 KB
39 AC 23 ms 804 KB
4 AC 26 ms 804 KB
40 AC 23 ms 804 KB
41 AC 25 ms 928 KB
42 AC 26 ms 932 KB
43 AC 26 ms 800 KB
44 AC 25 ms 800 KB
45 TLE
46 TLE
47 TLE
48 TLE
5 AC 27 ms 800 KB
6 AC 25 ms 804 KB
7 AC 28 ms 800 KB
8 TLE
9 TLE