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
Task D - 素数取りゲーム
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2097 Byte
Status
Exec Time 31 ms
Memory 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