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");