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 |
|
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 |