※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
처음엔 다소 어렵게 접근했었지만, 이 게임은 참가인원 수 보다 높은 소수를 출력하면 자신에게 절대로 돌아오지 않는 원리를 이용하여 쉽게 풀 수 있는 문제입니다. 단, 자기가 자기 자신을 가리키고 있거나, 특정 인물이 지목되지 않았을 경우에는 성립하지 않으므로 이를 체크하여 -1을 출력해 주면 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll w[1000001];
bool check[1000001];
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
if (i == w[i] || check[i]) return cout << "-1\n", 0;
check[i] = true;
}
cout << 1000003;
}