結果

問題 No.2551 2, 3, 5, 7 Game
ユーザー siganaisiganai
提出日時 2023-11-27 22:39:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 42 ms / 2,357 ms
コード長 17,379 bytes
コンパイル時間 4,419 ms
コンパイル使用メモリ 351,824 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2023-11-27 22:39:13
合計ジャッジ時間 5,547 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 3 ms
6,676 KB
testcase_02 AC 3 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 3 ms
6,676 KB
testcase_05 AC 40 ms
6,676 KB
testcase_06 AC 41 ms
6,676 KB
testcase_07 AC 40 ms
6,676 KB
testcase_08 AC 42 ms
6,676 KB
testcase_09 AC 28 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC target("avx,avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vs = vector<string>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(a,b,c,name,...) name
#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)
#define rrep4(i,a,b,c) for(ll i = (a) + ((b)-(a)-1) / (c) * (c);i >= (a);i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(i) begin(i) , end(i)
#define all2(i,a) begin(i) , begin(i) + a
#define all3(i,a,b) begin(i) + a , begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){return *min_element(all(a));}
template<class T> auto max(const T& a){return *max_element(all(a));}
template<class... Ts> void in(Ts&... t);
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
ll intpow(ll a, ll b){ ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}
ll modpow(ll a, ll b, ll p){ ll ans = 1; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll GCD(ll a,ll b) { if(a == 0 || b == 0) return 0; if(a % b == 0) return b; else return GCD(b,a%b);}
ll LCM(ll a,ll b) { if(a == 0) return b; if(b == 0) return a;return a / GCD(a,b) * b;}
void Yes() {cout << "Yes\n";return;}
void No() {cout << "No\n";return;}
void YES() {cout << "YES\n";return;}
void NO() {cout << "NO\n";return;}
namespace IO{
#define VOID(a) decltype(void(a))
struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(12);}} setting;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){in(get<idx>(t)...);}
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ituple(t, make_index_sequence<tuple_size<T>::value>{});} 
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }

#undef unpack
static const double PI = 3.1415926535897932;
template <class F> struct REC {
    F f;
    REC(F &&f_) : f(forward<F>(f_)) {}
    template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};

constexpr int mod = 998244353;
//constexpr int mod = 1000000007;
map<ll,string> memo;
void solve() {
    LL(n);
    map<ll,int> mp;
    auto dfs = REC([&](auto &&f,ll M,int c) -> int {
        if(M * 2 >= n) {
            return c;
        }
        if(mp.find(M) != mp.end()) return mp[M];
        int flg = -1;
        if(M * 2 < n) {
            int x = f(M * 2,1 - c);
            if(x != c) {
                flg = x;
            }
        }
        if(M * 3 < n) {
            int x = f(M * 3,1 - c);
            if(x != c) {
                flg = x;
            }
        }
        if(M * 5 < n) {
            int x = f(M * 5,1 - c);
            if(x != c) {
                flg = x;
            }
        }
        if(M * 7 < n) {
            int x = f(M * 7,1 - c);
            if(x != c) {
                flg = x;
            }
        }
        if(flg == -1) flg = c;
        return mp[M] = flg;
    });
    //int x = dfs(1,0);
    //cout << n << " ";
    auto it = memo.lower_bound(n);
    cout << it->second << '\n';
}
int main() {
    /*
    ll M = intpow(10,16);
    vl dat;
    rep(i,54) {
        ll XI = intpow(2,i);
        rep(j,1) {
            if(XI * intpow(3,j) > M) break;
            ll XJ = XI * intpow(3,j);
            rep(k,1) {
                if(XJ * intpow(5,k) > M) break;
                ll XK = XJ * intpow(5,k);
                rep(l,20) {
                    if(XK * intpow(7,l) > M) break;
                    ll XL = XK * intpow(7,l);
                    dat.emplace_back(XL);
                }
            }
        }
    }
    sort(all(dat));
    cout << dat.size() << '\n';
    for(auto &x:dat) {
        cout << x << '\n';
    }
    */
    memo = {{1,"ryota"},{2,"ryota"},{4,"sepa"},{7,"sepa"},{8,"sepa"},{14,"sepa"},{16,"ryota"},{28,"ryota"},{32,"sepa"},{49,"sepa"},{56,"sepa"},{64,"sepa"},{98,"sepa"},{112,"sepa"},{128,"sepa"},{196,"sepa"},{224,"ryota"},{256,"ryota"},{343,"ryota"},{392,"ryota"},{448,"sepa"},{512,"sepa"},{686,"sepa"},{784,"sepa"},{896,"sepa"},{1024,"sepa"},{1372,"sepa"},{1568,"sepa"},{1792,"sepa"},{2048,"sepa"},{2401,"sepa"},{2744,"sepa"},{3136,"ryota"},{3584,"ryota"},{4096,"ryota"},{4802,"ryota"},{5488,"ryota"},{6272,"sepa"},{7168,"sepa"},{8192,"sepa"},{9604,"sepa"},{10976,"sepa"},{12544,"sepa"},{14336,"sepa"},{16384,"sepa"},{16807,"sepa"},{19208,"sepa"},{21952,"sepa"},{25088,"sepa"},{28672,"sepa"},{32768,"sepa"},{33614,"sepa"},{38416,"sepa"},{43904,"ryota"},{50176,"ryota"},{57344,"ryota"},{65536,"ryota"},{67228,"ryota"},{76832,"ryota"},{87808,"sepa"},{100352,"sepa"},{114688,"sepa"},{117649,"sepa"},{131072,"sepa"},{134456,"sepa"},{153664,"sepa"},{175616,"sepa"},{200704,"sepa"},{229376,"sepa"},{235298,"sepa"},{262144,"sepa"},{268912,"sepa"},{307328,"sepa"},{351232,"sepa"},{401408,"sepa"},{458752,"sepa"},{470596,"sepa"},{524288,"sepa"},{537824,"sepa"},{614656,"ryota"},{702464,"ryota"},{802816,"ryota"},{823543,"ryota"},{917504,"ryota"},{941192,"ryota"},{1048576,"ryota"},{1075648,"ryota"},{1229312,"sepa"},{1404928,"sepa"},{1605632,"sepa"},{1647086,"sepa"},{1835008,"sepa"},{1882384,"sepa"},{2097152,"sepa"},{2151296,"sepa"},{2458624,"sepa"},{2809856,"sepa"},{3211264,"sepa"},{3294172,"sepa"},{3670016,"sepa"},{3764768,"sepa"},{4194304,"sepa"},{4302592,"sepa"},{4917248,"sepa"},{5619712,"sepa"},{5764801,"sepa"},{6422528,"sepa"},{6588344,"sepa"},{7340032,"sepa"},{7529536,"sepa"},{8388608,"ryota"},{8605184,"ryota"},{9834496,"ryota"},{11239424,"ryota"},{11529602,"ryota"},{12845056,"ryota"},{13176688,"ryota"},{14680064,"ryota"},{15059072,"ryota"},{16777216,"sepa"},{17210368,"sepa"},{19668992,"sepa"},{22478848,"sepa"},{23059204,"sepa"},{25690112,"sepa"},{26353376,"sepa"},{29360128,"sepa"},{30118144,"sepa"},{33554432,"sepa"},{34420736,"sepa"},{39337984,"sepa"},{40353607,"sepa"},{44957696,"sepa"},{46118408,"sepa"},{51380224,"sepa"},{52706752,"sepa"},{58720256,"sepa"},{60236288,"sepa"},{67108864,"sepa"},{68841472,"sepa"},{78675968,"sepa"},{80707214,"sepa"},{89915392,"sepa"},{92236816,"sepa"},{102760448,"sepa"},{105413504,"sepa"},{117440512,"ryota"},{120472576,"ryota"},{134217728,"ryota"},{137682944,"ryota"},{157351936,"ryota"},{161414428,"ryota"},{179830784,"ryota"},{184473632,"ryota"},{205520896,"ryota"},{210827008,"ryota"},{234881024,"sepa"},{240945152,"sepa"},{268435456,"sepa"},{275365888,"sepa"},{282475249,"sepa"},{314703872,"sepa"},{322828856,"sepa"},{359661568,"sepa"},{368947264,"sepa"},{411041792,"sepa"},{421654016,"sepa"},{469762048,"sepa"},{481890304,"sepa"},{536870912,"sepa"},{550731776,"sepa"},{564950498,"sepa"},{629407744,"sepa"},{645657712,"sepa"},{719323136,"sepa"},{737894528,"sepa"},{822083584,"sepa"},{843308032,"sepa"},{939524096,"sepa"},{963780608,"sepa"},{1073741824,"sepa"},{1101463552,"sepa"},{1129900996,"sepa"},{1258815488,"sepa"},{1291315424,"sepa"},{1438646272,"sepa"},{1475789056,"sepa"},{1644167168,"ryota"},{1686616064,"ryota"},{1879048192,"ryota"},{1927561216,"ryota"},{1977326743,"ryota"},{2147483648,"ryota"},{2202927104,"ryota"},{2259801992,"ryota"},{2517630976,"ryota"},{2582630848,"ryota"},{2877292544,"ryota"},{2951578112,"ryota"},{3288334336,"sepa"},{3373232128,"sepa"},{3758096384,"sepa"},{3855122432,"sepa"},{3954653486,"sepa"},{4294967296,"sepa"},{4405854208,"sepa"},{4519603984,"sepa"},{5035261952,"sepa"},{5165261696,"sepa"},{5754585088,"sepa"},{5903156224,"sepa"},{6576668672,"sepa"},{6746464256,"sepa"},{7516192768,"sepa"},{7710244864,"sepa"},{7909306972,"sepa"},{8589934592,"sepa"},{8811708416,"sepa"},{9039207968,"sepa"},{10070523904,"sepa"},{10330523392,"sepa"},{11509170176,"sepa"},{11806312448,"sepa"},{13153337344,"sepa"},{13492928512,"sepa"},{13841287201,"sepa"},{15032385536,"sepa"},{15420489728,"sepa"},{15818613944,"sepa"},{17179869184,"sepa"},{17623416832,"sepa"},{18078415936,"sepa"},{20141047808,"sepa"},{20661046784,"sepa"},{23018340352,"ryota"},{23612624896,"ryota"},{26306674688,"ryota"},{26985857024,"ryota"},{27682574402,"ryota"},{30064771072,"ryota"},{30840979456,"ryota"},{31637227888,"ryota"},{34359738368,"ryota"},{35246833664,"ryota"},{36156831872,"ryota"},{40282095616,"ryota"},{41322093568,"ryota"},{46036680704,"sepa"},{47225249792,"sepa"},{52613349376,"sepa"},{53971714048,"sepa"},{55365148804,"sepa"},{60129542144,"sepa"},{61681958912,"sepa"},{63274455776,"sepa"},{68719476736,"sepa"},{70493667328,"sepa"},{72313663744,"sepa"},{80564191232,"sepa"},{82644187136,"sepa"},{92073361408,"sepa"},{94450499584,"sepa"},{96889010407,"sepa"},{105226698752,"sepa"},{107943428096,"sepa"},{110730297608,"sepa"},{120259084288,"sepa"},{123363917824,"sepa"},{126548911552,"sepa"},{137438953472,"sepa"},{140987334656,"sepa"},{144627327488,"sepa"},{161128382464,"sepa"},{165288374272,"sepa"},{184146722816,"sepa"},{188900999168,"sepa"},{193778020814,"sepa"},{210453397504,"sepa"},{215886856192,"sepa"},{221460595216,"sepa"},{240518168576,"sepa"},{246727835648,"sepa"},{253097823104,"sepa"},{274877906944,"sepa"},{281974669312,"sepa"},{289254654976,"sepa"},{322256764928,"ryota"},{330576748544,"ryota"},{368293445632,"ryota"},{377801998336,"ryota"},{387556041628,"ryota"},{420906795008,"ryota"},{431773712384,"ryota"},{442921190432,"ryota"},{481036337152,"ryota"},{493455671296,"ryota"},{506195646208,"ryota"},{549755813888,"ryota"},{563949338624,"ryota"},{578509309952,"ryota"},{644513529856,"sepa"},{661153497088,"sepa"},{678223072849,"sepa"},{736586891264,"sepa"},{755603996672,"sepa"},{775112083256,"sepa"},{841813590016,"sepa"},{863547424768,"sepa"},{885842380864,"sepa"},{962072674304,"sepa"},{986911342592,"sepa"},{1012391292416,"sepa"},{1099511627776,"sepa"},{1127898677248,"sepa"},{1157018619904,"sepa"},{1289027059712,"sepa"},{1322306994176,"sepa"},{1356446145698,"sepa"},{1473173782528,"sepa"},{1511207993344,"sepa"},{1550224166512,"sepa"},{1683627180032,"sepa"},{1727094849536,"sepa"},{1771684761728,"sepa"},{1924145348608,"sepa"},{1973822685184,"sepa"},{2024782584832,"sepa"},{2199023255552,"sepa"},{2255797354496,"sepa"},{2314037239808,"sepa"},{2578054119424,"sepa"},{2644613988352,"sepa"},{2712892291396,"sepa"},{2946347565056,"sepa"},{3022415986688,"sepa"},{3100448333024,"sepa"},{3367254360064,"sepa"},{3454189699072,"sepa"},{3543369523456,"sepa"},{3848290697216,"sepa"},{3947645370368,"sepa"},{4049565169664,"sepa"},{4398046511104,"ryota"},{4511594708992,"ryota"},{4628074479616,"ryota"},{4747561509943,"ryota"},{5156108238848,"ryota"},{5289227976704,"ryota"},{5425784582792,"ryota"},{5892695130112,"ryota"},{6044831973376,"ryota"},{6200896666048,"ryota"},{6734508720128,"ryota"},{6908379398144,"ryota"},{7086739046912,"ryota"},{7696581394432,"ryota"},{7895290740736,"ryota"},{8099130339328,"ryota"},{8796093022208,"sepa"},{9023189417984,"sepa"},{9256148959232,"sepa"},{9495123019886,"sepa"},{10312216477696,"sepa"},{10578455953408,"sepa"},{10851569165584,"sepa"},{11785390260224,"sepa"},{12089663946752,"sepa"},{12401793332096,"sepa"},{13469017440256,"sepa"},{13816758796288,"sepa"},{14173478093824,"sepa"},{15393162788864,"sepa"},{15790581481472,"sepa"},{16198260678656,"sepa"},{17592186044416,"sepa"},{18046378835968,"sepa"},{18512297918464,"sepa"},{18990246039772,"sepa"},{20624432955392,"sepa"},{21156911906816,"sepa"},{21703138331168,"sepa"},{23570780520448,"sepa"},{24179327893504,"sepa"},{24803586664192,"sepa"},{26938034880512,"sepa"},{27633517592576,"sepa"},{28346956187648,"sepa"},{30786325577728,"sepa"},{31581162962944,"sepa"},{32396521357312,"sepa"},{33232930569601,"sepa"},{35184372088832,"sepa"},{36092757671936,"sepa"},{37024595836928,"sepa"},{37980492079544,"sepa"},{41248865910784,"sepa"},{42313823813632,"sepa"},{43406276662336,"sepa"},{47141561040896,"sepa"},{48358655787008,"sepa"},{49607173328384,"sepa"},{53876069761024,"sepa"},{55267035185152,"sepa"},{56693912375296,"sepa"},{61572651155456,"ryota"},{63162325925888,"ryota"},{64793042714624,"ryota"},{66465861139202,"ryota"},{70368744177664,"ryota"},{72185515343872,"ryota"},{74049191673856,"ryota"},{75960984159088,"ryota"},{82497731821568,"ryota"},{84627647627264,"ryota"},{86812553324672,"ryota"},{94283122081792,"ryota"},{96717311574016,"ryota"},{99214346656768,"ryota"},{107752139522048,"ryota"},{110534070370304,"ryota"},{113387824750592,"ryota"},{123145302310912,"sepa"},{126324651851776,"sepa"},{129586085429248,"sepa"},{132931722278404,"sepa"},{140737488355328,"sepa"},{144371030687744,"sepa"},{148098383347712,"sepa"},{151921968318176,"sepa"},{164995463643136,"sepa"},{169255295254528,"sepa"},{173625106649344,"sepa"},{188566244163584,"sepa"},{193434623148032,"sepa"},{198428693313536,"sepa"},{215504279044096,"sepa"},{221068140740608,"sepa"},{226775649501184,"sepa"},{232630513987207,"sepa"},{246290604621824,"sepa"},{252649303703552,"sepa"},{259172170858496,"sepa"},{265863444556808,"sepa"},{281474976710656,"sepa"},{288742061375488,"sepa"},{296196766695424,"sepa"},{303843936636352,"sepa"},{329990927286272,"sepa"},{338510590509056,"sepa"},{347250213298688,"sepa"},{377132488327168,"sepa"},{386869246296064,"sepa"},{396857386627072,"sepa"},{431008558088192,"sepa"},{442136281481216,"sepa"},{453551299002368,"sepa"},{465261027974414,"sepa"},{492581209243648,"sepa"},{505298607407104,"sepa"},{518344341716992,"sepa"},{531726889113616,"sepa"},{562949953421312,"sepa"},{577484122750976,"sepa"},{592393533390848,"sepa"},{607687873272704,"sepa"},{659981854572544,"sepa"},{677021181018112,"sepa"},{694500426597376,"sepa"},{754264976654336,"sepa"},{773738492592128,"sepa"},{793714773254144,"sepa"},{862017116176384,"ryota"},{884272562962432,"ryota"},{907102598004736,"ryota"},{930522055948828,"ryota"},{985162418487296,"ryota"},{1010597214814208,"ryota"},{1036688683433984,"ryota"},{1063453778227232,"ryota"},{1125899906842624,"ryota"},{1154968245501952,"ryota"},{1184787066781696,"ryota"},{1215375746545408,"ryota"},{1319963709145088,"ryota"},{1354042362036224,"ryota"},{1389000853194752,"ryota"},{1508529953308672,"ryota"},{1547476985184256,"ryota"},{1587429546508288,"ryota"},{1628413597910449,"sepa"},{1724034232352768,"sepa"},{1768545125924864,"sepa"},{1814205196009472,"sepa"},{1861044111897656,"sepa"},{1970324836974592,"sepa"},{2021194429628416,"sepa"},{2073377366867968,"sepa"},{2126907556454464,"sepa"},{2251799813685248,"sepa"},{2309936491003904,"sepa"},{2369574133563392,"sepa"},{2430751493090816,"sepa"},{2639927418290176,"sepa"},{2708084724072448,"sepa"},{2778001706389504,"sepa"},{3017059906617344,"sepa"},{3094953970368512,"sepa"},{3174859093016576,"sepa"},{3256827195820898,"sepa"},{3448068464705536,"sepa"},{3537090251849728,"sepa"},{3628410392018944,"sepa"},{3722088223795312,"sepa"},{3940649673949184,"sepa"},{4042388859256832,"sepa"},{4146754733735936,"sepa"},{4253815112908928,"sepa"},{4503599627370496,"sepa"},{4619872982007808,"sepa"},{4739148267126784,"sepa"},{4861502986181632,"sepa"},{5279854836580352,"sepa"},{5416169448144896,"sepa"},{5556003412779008,"sepa"},{6034119813234688,"sepa"},{6189907940737024,"sepa"},{6349718186033152,"sepa"},{6513654391641796,"sepa"},{6896136929411072,"sepa"},{7074180503699456,"sepa"},{7256820784037888,"sepa"},{7444176447590624,"sepa"},{7881299347898368,"sepa"},{8084777718513664,"sepa"},{8293509467471872,"sepa"},{8507630225817856,"sepa"},{9007199254740992,"sepa"},{9239745964015616,"sepa"},{9478296534253568,"sepa"},{9723005972363264,"sepa"},{10000000000000000,"sepa"}};
    INT(TT);
    while(TT--) solve();
}
0