Codechef PERMUT2解决方案

Question

以下网站有问题。

http://www.codechef.com/problems/PERMUT2

我一直在试图为PERMUT2代码解决方案。我的下面的解决方案在某些测试用例上失败。请帮助我发现下面的代码中的缺陷。

#include <stdio.h> 

int a[100000]; 

int main() 
{ 
    int i, j, n, ret; 
    while(1) 
    { 
     scanf("%d", &n); 
     if(n == 0) 
      break; 
     ret = 0; 
     for(i = 0; i < n; i++) 
      scanf("%d", &a[i]); 
     for(i = 0; i < n; i++) 
      if(a[i] != i + 1) 
       ret++; 
     if(ret % 2 == 0) 
      printf("ambiguous\n"); 
     else 
      printf("not ambiguous\n"); 
    } 
    return 0; 
} 

Answer 1

您没有检查正确的属性。 if(a[i] != i + 1) ret++;是不正确的检查。

您要检查a[a[i] - 1] == i + 1阵列上的所有元素：

bool ambiguous = true; 
for(i = 0; i < n; i++) { 
    if (a[a[i] - 1] != i + 1) { 
     ambiguous = false; 
     break; 
    } 
} 
if(ambiguous) 
    printf("ambiguous\n"); 
else 
    printf("not ambiguous\n");