Submission #3930675

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair



inline int bin_keta(ll x) {
    return 64 - __builtin_clzll(x);
}

ll q(int t, int a, int k) {
    ll res = 1;
    rep(i,k) {
        res <<= 1LL;
        if (i % 2 == 0) res |= (ll)t;
        else            res |= (ll)a;
    }
    res = (1LL << (ll)k) | res;
    return res;
}

bool solve(ll N) {
    if (N < 2) return false;

    int k = bin_keta(N) - 1;
    if (k % 2 == 1) {
        ll best = q(0,1,k);
        return best <= N;
    } else {
        ll best = q(1,0,k);
        return best > N;
    }
}

int main() {
    ll N; cin >> N;
    cout << (solve(N) ? "Takahashi":"Aoki") << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 倍々ゲーム
User naoya_t
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2063 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All 100 / 100 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt, subtask1_48.txt, subtask1_49.txt, subtask1_50.txt, subtask1_51.txt, subtask1_52.txt, subtask1_53.txt, subtask1_54.txt, subtask1_55.txt, subtask1_56.txt, subtask1_57.txt, subtask1_58.txt, subtask1_59.txt, subtask1_60.txt, subtask1_61.txt, subtask1_62.txt, subtask1_63.txt, subtask1_64.txt, subtask1_65.txt, subtask1_66.txt, subtask1_67.txt, subtask1_68.txt, subtask1_69.txt, subtask1_70.txt, subtask1_71.txt, subtask1_72.txt, subtask1_73.txt, subtask1_74.txt, subtask1_75.txt, subtask1_76.txt, subtask1_77.txt, subtask1_78.txt, subtask1_79.txt, subtask1_80.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
sample_05.txt 1 ms 256 KB
subtask1_01.txt 1 ms 256 KB
subtask1_02.txt 1 ms 256 KB
subtask1_03.txt 1 ms 256 KB
subtask1_04.txt 1 ms 256 KB
subtask1_05.txt 1 ms 256 KB
subtask1_06.txt 1 ms 256 KB
subtask1_07.txt 1 ms 256 KB
subtask1_08.txt 1 ms 256 KB
subtask1_09.txt 1 ms 256 KB
subtask1_10.txt 1 ms 256 KB
subtask1_11.txt 1 ms 256 KB
subtask1_12.txt 1 ms 256 KB
subtask1_13.txt 1 ms 256 KB
subtask1_14.txt 1 ms 256 KB
subtask1_15.txt 1 ms 256 KB
subtask1_16.txt 1 ms 256 KB
subtask1_17.txt 1 ms 256 KB
subtask1_18.txt 1 ms 256 KB
subtask1_19.txt 1 ms 256 KB
subtask1_20.txt 1 ms 256 KB
subtask1_21.txt 1 ms 256 KB
subtask1_22.txt 1 ms 256 KB
subtask1_23.txt 1 ms 256 KB
subtask1_24.txt 1 ms 256 KB
subtask1_25.txt 1 ms 256 KB
subtask1_26.txt 1 ms 256 KB
subtask1_27.txt 1 ms 256 KB
subtask1_28.txt 1 ms 256 KB
subtask1_29.txt 1 ms 256 KB
subtask1_30.txt 1 ms 256 KB
subtask1_31.txt 1 ms 256 KB
subtask1_32.txt 1 ms 256 KB
subtask1_33.txt 1 ms 256 KB
subtask1_34.txt 1 ms 256 KB
subtask1_35.txt 1 ms 256 KB
subtask1_36.txt 1 ms 256 KB
subtask1_37.txt 1 ms 256 KB
subtask1_38.txt 1 ms 256 KB
subtask1_39.txt 1 ms 256 KB
subtask1_40.txt 1 ms 256 KB
subtask1_41.txt 1 ms 256 KB
subtask1_42.txt 1 ms 256 KB
subtask1_43.txt 1 ms 256 KB
subtask1_44.txt 1 ms 256 KB
subtask1_45.txt 1 ms 256 KB
subtask1_46.txt 1 ms 256 KB
subtask1_47.txt 1 ms 256 KB
subtask1_48.txt 1 ms 256 KB
subtask1_49.txt 1 ms 256 KB
subtask1_50.txt 1 ms 256 KB
subtask1_51.txt 1 ms 256 KB
subtask1_52.txt 1 ms 256 KB
subtask1_53.txt 1 ms 256 KB
subtask1_54.txt 1 ms 256 KB
subtask1_55.txt 1 ms 256 KB
subtask1_56.txt 1 ms 256 KB
subtask1_57.txt 1 ms 256 KB
subtask1_58.txt 1 ms 256 KB
subtask1_59.txt 1 ms 256 KB
subtask1_60.txt 1 ms 256 KB
subtask1_61.txt 1 ms 256 KB
subtask1_62.txt 1 ms 256 KB
subtask1_63.txt 1 ms 256 KB
subtask1_64.txt 1 ms 256 KB
subtask1_65.txt 1 ms 256 KB
subtask1_66.txt 1 ms 256 KB
subtask1_67.txt 1 ms 256 KB
subtask1_68.txt 1 ms 256 KB
subtask1_69.txt 1 ms 256 KB
subtask1_70.txt 1 ms 256 KB
subtask1_71.txt 1 ms 256 KB
subtask1_72.txt 1 ms 256 KB
subtask1_73.txt 1 ms 256 KB
subtask1_74.txt 1 ms 256 KB
subtask1_75.txt 1 ms 256 KB
subtask1_76.txt 1 ms 256 KB
subtask1_77.txt 1 ms 256 KB
subtask1_78.txt 1 ms 256 KB
subtask1_79.txt 1 ms 256 KB
subtask1_80.txt 1 ms 256 KB