글 읽기 - 시간오류가 나가서 고쳤는데..

wnsgurl97 2년 전 0

이번엔 어디가 문제일까요 ㅠㅠ 반례나 오류 혹시 찾아주실수 있나요ㅜㅜ

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define FOR2(i, n) for(int i = 0; i < n; ++i)
#define FOR3(i, n, m) for(int i = n; i < m ; ++i)
using namespace std;

bool isPrime[1005];
bool isPick[50];
int arr[55], N;
vector<int> ans;

bool DFS(int cnt) {

	if (cnt == 0)
		return true;

	int target;
	FOR2(i, N) {
		if (!isPick[i]) {
			target = i;
			isPick[target] = true;
			break;
		}
	}

	FOR2(i, N) {
		if (!isPick[i] && isPrime[arr[target] + arr[i]]) {
			isPick[i] = true;
			if (DFS(cnt - 2)) {
				if (target == 0)
					ans.push_back(arr[i]);
				else {
					isPick[i] = false;
					isPick[target] = false;
					return true;
				}
			}
			isPick[i] = false;
		}
	}

	isPick[target] = false;
	return false;
}

void findPrime(int p) {
	FOR3(i, 2, 505) {
		if (p * i >= 1005)
			return;
		isPrime[p * i] = false;
	}
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(isPrime, true, 1005);
	isPrime[1] = false;
	FOR3(i, 2, 1005){
		if(isPrime[i])
			findPrime(i);
	}

	cin >> N;
	FOR2(i, N) {
		cin >> arr[i];
	}

	DFS(N);

	if (ans.empty())
		cout << -1 << '\n';
	else {
		sort(ans.begin(), ans.end());
		FOR2(i, ans.size()) {
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간오류가 나가서 고쳤는데..

wnsgurl97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말