#1002627 (C++14) No.761 平均値ゲーム

提出ソース

結果

問題	No.761 平均値ゲーム
ユーザー	au7777
提出日時	2024-08-21 01:50:21
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	75 ms / 2,000 ms
コード長	3,960 bytes
コンパイル時間	5,034 ms
コンパイル使用メモリ	246,512 KB
実行使用メモリ	8,908 KB
最終ジャッジ日時	2024-08-21 01:50:33
合計ジャッジ時間	12,120 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	1 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	54 ms 6,940 KB
testcase_34	AC	62 ms 6,940 KB
testcase_35	AC	7 ms 6,944 KB
testcase_36	AC	35 ms 6,940 KB
testcase_37	AC	53 ms 6,944 KB
testcase_38	AC	51 ms 6,940 KB
testcase_39	AC	65 ms 6,940 KB
testcase_40	AC	64 ms 6,944 KB
testcase_41	AC	61 ms 6,944 KB
testcase_42	AC	69 ms 6,944 KB
testcase_43	AC	13 ms 6,944 KB
testcase_44	AC	42 ms 6,940 KB
testcase_45	AC	59 ms 6,940 KB
testcase_46	AC	32 ms 6,940 KB
testcase_47	AC	34 ms 6,944 KB
testcase_48	AC	5 ms 6,944 KB
testcase_49	AC	67 ms 6,940 KB
testcase_50	AC	10 ms 6,944 KB
testcase_51	AC	7 ms 6,944 KB
testcase_52	AC	7 ms 6,940 KB
testcase_53	AC	67 ms 6,940 KB
testcase_54	AC	38 ms 6,940 KB
testcase_55	AC	68 ms 6,940 KB
testcase_56	AC	21 ms 6,944 KB
testcase_57	AC	67 ms 6,940 KB
testcase_58	AC	12 ms 6,940 KB
testcase_59	AC	63 ms 6,940 KB
testcase_60	AC	20 ms 6,940 KB
testcase_61	AC	72 ms 6,940 KB
testcase_62	AC	68 ms 6,944 KB
testcase_63	AC	14 ms 6,944 KB
testcase_64	AC	62 ms 6,944 KB
testcase_65	AC	26 ms 6,940 KB
testcase_66	AC	6 ms 6,940 KB
testcase_67	AC	21 ms 6,940 KB
testcase_68	AC	9 ms 6,940 KB
testcase_69	AC	55 ms 6,944 KB
testcase_70	AC	37 ms 6,944 KB
testcase_71	AC	17 ms 6,944 KB
testcase_72	AC	8 ms 6,944 KB
testcase_73	AC	23 ms 6,940 KB
testcase_74	AC	15 ms 6,944 KB
testcase_75	AC	31 ms 6,940 KB
testcase_76	AC	20 ms 6,940 KB
testcase_77	AC	52 ms 6,940 KB
testcase_78	AC	35 ms 6,944 KB
testcase_79	AC	13 ms 6,940 KB
testcase_80	AC	11 ms 6,940 KB
testcase_81	AC	10 ms 6,940 KB
testcase_82	AC	43 ms 6,944 KB
testcase_83	AC	74 ms 6,944 KB
testcase_84	AC	71 ms 6,940 KB
testcase_85	AC	73 ms 6,944 KB
testcase_86	AC	75 ms 6,944 KB
testcase_87	AC	75 ms 6,944 KB
testcase_88	AC	74 ms 6,940 KB
testcase_89	AC	73 ms 6,944 KB
testcase_90	AC	73 ms 6,940 KB
testcase_91	AC	71 ms 6,944 KB
testcase_92	AC	73 ms 6,944 KB
testcase_93	AC	2 ms 6,940 KB
testcase_94	AC	2 ms 6,944 KB
testcase_95	AC	45 ms 6,940 KB
testcase_96	AC	56 ms 6,944 KB
testcase_97	AC	51 ms 6,944 KB
testcase_98	AC	54 ms 8,908 KB
testcase_99	AC	72 ms 8,728 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
typedef long long int ll;
using namespace std;
typedef pair<ll, ll> P;
using namespace atcoder;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
#define USE998244353
#ifdef USE998244353
const ll MOD = 998244353;
using mint = modint998244353;
#else
const ll MOD = 1000000007;
using mint = modint1000000007;
#endif

#pragma region //使いがち
const int MAX = 2000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll pow_ll(ll x, ll n) {
    if (n == 0) return 1;
    if (n % 2) {
        return pow_ll(x, n - 1) * x;
    }
    else {
        ll tmp = pow_ll(x, n / 2);
        return tmp * tmp;
    }
}
// floor(a^(1/k))
ll floor_root(ll a, ll k) {
    assert(a >= 0);
    assert(k >= 1);
    if (a == 0) return 0;
    if (k == 1) return a;
    // 大体の値
    ll x = (ll)pow(a, 1.0 / k);
    // 増やす
    while ((pow_ll(x + 1, k)) <= a) {
        x++;
    }
    // 減らす
    while ((pow_ll(x, k)) > a) {
        x--;
    }
    return x;
}
ll keta(ll num, ll arity) {
    ll ret = 0;
    while (num) {
        num /= arity;
        ret++;
    }
    return ret;
}
// k進数で見た時のi桁目の数を返す (一番下は0桁目)
ll keta_num(ll num, ll i, ll k) {
    return (num / pow_ll(k, i)) % k;
}
ll ceil(ll n, ll m) {
    // n > 0, m > 0
    ll ret = n / m;
    if (n % m) ret++;
    return ret;
}
void compress(vector<ll>& v) {
    // [3 5 5 6 1 1 10 1] -> [1 2 2 3 0 0 4 0] 
    vector<ll> u = v;
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(),u.end()),u.end());
    map<ll, ll> mp;
    for (int i = 0; i < u.size(); i++) {
        mp[u[i]] = i;
    }
    for (int i = 0; i < v.size(); i++) {
        v[i] = mp[v[i]];
    }
}
vector<pair<ll, ll> > prime_factorize(ll N) {
    vector<pair<ll, ll> > res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
#pragma endregion

// 1以上n以下について素数かどうかのリストを返す
vector<bool> is_prime_list(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i * 2; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
    return is_prime;
}

// この盤面を与えられた時に先手が勝てるかどうかを返す
bool win(vector<ll>& v) {
    int n = v.size();
    if (n == 0) {
        return false;
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += v[i];
    }
    int i;
    for (i = 0; i < n; i++) {
        if (v[i] * (ll)n >= sum) {
            break;
        }
    }
    vector<ll> s;
    vector<ll> b;
    for (int j = 0; j < i; j++) {
        s.push_back(v[j]);
    }
    for (int j = i; j < n; j++) {
        b.push_back(v[j]);
    }

    if (s.size() == 0 || b.size() == 0) {
        return true;
    }

    bool win1 = win(s);
    bool win2 = win(b);
    return !win1 || !win2;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (win(a)) {
        cout << "First" << endl;
    }
    else {
        cout << "Second" << endl;
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード