結果

問題 No.308 素数は通れません
ユーザー hirokazu1020
提出日時 2015-12-03 21:03:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,651 bytes
コンパイル時間 1,357 ms
コンパイル使用メモリ 107,464 KB
実行使用メモリ 49,964 KB
最終ジャッジ日時 2024-09-14 08:32:13
合計ジャッジ時間 27,379 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())
#define indexOf(v,x) (find(all(v),x)-v.begin())


#define MAX_N 1000000
int prime[MAX_N];
bool is_prime[MAX_N + 1];
int sieve(int n) {
	int p = 0;
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i)is_prime[j] = false;
		}
	}
	return p;
}



long long n;


bool f(int w) {
	int dy[] = { 1,0,0,-1 };
	int dx[] = { 0,-1,1,0 };
	set<pair<int, int>> v;
	v.insert(make_pair(0,0));
	queue<pair<int, int>> q;
	int gy=(n-1)/w, gx=(n-1)%w;
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		pair<int, int> a, b;
		a = q.front(); q.pop();
		rep(i,4) {
			b = a;
			b.first += dy[i];
			b.second += dx[i];
			int m = b.first*w + b.second + 1;
			if (n < m || b.first < 0 || b.second < 0 || w <= b.second)continue;
			if (v.find(b) != v.end() || is_prime[m])continue;
			v.insert(b);
			q.push(b);
			if (m == n || m>MAX_N-w)return true;
		}
	}

	return false;
}

int main() {
	sieve(MAX_N);
	cin >> n;
	for (int w = 3;;w++) {
		if (f(w)) {
			cout << w << endl;
			break;
		}
	}
	return 0;
}
0