Contest Duration: ~ (local time) (300 minutes) Back to Home

Submission #7225749

Source Code Expand

Copy
```#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
vector<bool> makePrimesBool(int n) { // [2,n]
vector<bool> pr(n + 1, 1);
pr[0] = pr[1] = 0;
rep(p, 2, sqrt(n) + 2) if (pr[p]) for (int x = p * 2; x <= n; x += p) pr[x] = 0;
return pr;
}
/*---------------------------------------------------------------------------------------------------
∧＿∧
∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
（ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
／　　　＼　 　  |　|
/　　 /￣￣￣￣/　　|
＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, A[201010];
int grundy[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
rep(i, 0, N) cin >> A[i];

auto pr = makePrimesBool(1010101);
rep(i, 1, 1010101) if(pr[i]) {
set<int> gr;
gr.insert(0); // get i
if (0 < i - 2 and pr[i - 2]) {
gr.insert(grundy[i - 2]); // get 2
gr.insert(grundy[2]); // get i-2
}
while(gr.count(grundy[i])) grundy[i]++;
}

int xo = 0;
rep(i, 0, N) xo ^= grundy[A[i]];

if(xo == 0) cout << "Ai" << endl;
else cout << "An" << endl;
}

```

#### Submission Info

Submission Time 2019-08-31 19:15:20+0900 D - 素数取りゲーム hamayanhamayan C++14 (GCC 5.4.1) 100 2097 Byte AC 31 ms 5120 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01, 00_sample_02, 00_sample_03
All 100 / 100 00_sample_01, 00_sample_02, 00_sample_03, 01_small_01, 01_small_02, 01_small_03, 01_small_04, 01_small_05, 01_small_06, 02_random_01, 02_random_02, 02_random_03, 02_random_04, 02_random_05, 02_random_06, 02_random_07, 02_random_08, 02_random_09, 02_random_10, 03_large_01, 03_large_02, 03_large_03, 03_large_04, 03_large_05, 03_large_06, 04_large_01, 04_large_02, 04_large_03, 04_large_04, 04_large_05, 04_large_06, 04_large_07, 04_large_08, 04_large_09, 04_large_10
Case Name Status Exec Time Memory
00_sample_01 13 ms 4480 KB
00_sample_02 13 ms 4480 KB
00_sample_03 13 ms 4480 KB
01_small_01 13 ms 4480 KB
01_small_02 13 ms 4480 KB
01_small_03 13 ms 4480 KB
01_small_04 13 ms 4480 KB
01_small_05 13 ms 4480 KB
01_small_06 13 ms 4480 KB
02_random_01 14 ms 4480 KB
02_random_02 13 ms 4480 KB
02_random_03 13 ms 4480 KB
02_random_04 13 ms 4480 KB
02_random_05 13 ms 4480 KB
02_random_06 27 ms 4992 KB
02_random_07 29 ms 5120 KB
02_random_08 26 ms 4992 KB
02_random_09 26 ms 4992 KB
02_random_10 23 ms 4736 KB
03_large_01 30 ms 5120 KB
03_large_02 25 ms 5120 KB
03_large_03 31 ms 5120 KB
03_large_04 31 ms 5120 KB
03_large_05 31 ms 5120 KB
03_large_06 31 ms 5120 KB
04_large_01 27 ms 4992 KB
04_large_02 27 ms 4864 KB
04_large_03 24 ms 4864 KB
04_large_04 28 ms 4992 KB
04_large_05 28 ms 4992 KB
04_large_06 29 ms 4992 KB
04_large_07 29 ms 4992 KB
04_large_08 22 ms 4736 KB
04_large_09 23 ms 4736 KB
04_large_10 26 ms 4864 KB