#include #include #include using namespace std; vector odd, even, R; int n, first, matched[55]; bool prime[55][55], visited[55]; //matched => odd -> even //visited => even bool is_prime(int p) { bool G[p + 1]; for(int i = 2; i <= p; i++) { G[i] = 1; } for(int i = 2; i < p; i++) { if(G[i]) { for(int j = i * i; j <= p; j += i) { G[j] = 0; } } } if(G[p]) { return 1; } else { return 0; } } bool DFS(int i) { for(unsigned long long j = 0; j < even.size(); j++) { if(prime[i][j] && !visited[j]) { visited[j] = true; if(matched[j] == -1 || DFS(matched[j])) { matched[j] = i; return true; } } } return false; } int main(void) { scanf("%d", &n); if(n % 2 == 1) { printf("-1"); return 0; } scanf("%d", &first); if(first % 2 == 1) { odd.push_back(first); } else { even.push_back(first); } for(int i = 1; i < n; i++) { int a; scanf("%d", &a); if(a % 2 == 1) { odd.push_back(a); } else { even.push_back(a); } } if(odd.size() != even.size()) { printf("-1"); return 0; } for(unsigned long long i = 0; i < odd.size(); i++) { for(unsigned long long j = 0; j < even.size(); j++) { prime[i][j] = is_prime(odd.at(i) + even.at(j)); } } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// if(first % 2 == 1) { for(unsigned long long i = 0; i < even.size(); i++) { if(!prime[0][i]) { continue; } for(int j = 0; j < odd.size(); j++) { visited[j] = 0; matched[j] = -1; } visited[i] = 1; matched[0] = i; bool flag = 1; for(unsigned long long j = 0; j < even.size(); j++) { if(prime[0][j]) { for(unsigned long long k = j; k < odd.size(); k++) { if(matched[k] == -1) { if(!DFS(k)) { flag = 0; break; } } } if(flag) { R.push_back(even.at(i)); } break; } } } } else { for(unsigned long long i = 0; i < odd.size(); i++) { bool flag = 1; for(int j = 0; j < even.size(); j++) { matched[j] = -1; visited[j] = 0; } visited[0] = 1; matched[i] = 0; if(prime[i][0]) { for(unsigned long long j = 0; j < odd.size(); j++) { if(matched[j] == -1) { if(!DFS(j)) { flag = 0; break; } } } if(flag) { R.push_back(odd.at(i)); } } } } if(R.empty()) { printf("-1"); return 0; } sort(R.begin(), R.end()); for(unsigned long long i = 0; i < R.size(); i++) { printf("%d ", R.at(i)); } return 0; }

제출 #72129

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: