結果

問題 No.308 素数は通れません
ユーザー hirokazu1020
提出日時 2015-12-05 21:26:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,779 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 101,008 KB
実行使用メモリ 43,264 KB
最終ジャッジ日時 2024-09-14 14:30:57
合計ジャッジ時間 18,014 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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>
#include<stack>
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 10000000
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 v[MAX_N + 1];

bool f(int w) {
	int dy[] = { -1,0,0,1 };
	int dx[] = { 0,-1,1,0 };
	memset(v, false, sizeof(v));
	v[1] = true;
	stack<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.top(); 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[m] || is_prime[m])continue;
			v[m] = true;
			q.push(b);
			if (m == n || m>MAX_N - w)return true;
		}
	}

	return false;
}

int main() {
	sieve(MAX_N);
	string s;
	stringstream ss;
	cin >> s;
	if (s.size()>18) {
		n = 1LL << 60;
	}
	else {
		ss << s;
		ss >> n;
	}
	for (int w = 3;; w++) {
		if (f(w)) {
			cout << w << endl;
			break;
		}
	}
	return 0;
}
0