Sqrt Nim

Run Settings
LanguageC++
Language Version
Run Command
#include <bits/stdc++.h> using namespace std; // type #define int long long typedef long long ll; typedef long double ld; // loop //#define For(i, l, r, x) for (int i = l; i < r; i+=x) //#define ForE(i, l, r, x) for (int i = l; i <= r; i+=x) //#define Ford(i, r, l) for (int i = r; i > l; i--) //#define FordE(i, r, l) for (int i = r; i >= l; i--) //#define Fora(i, a) for (auto i : a) // I/O #define openfile(file) freopen(file".in", "r", stdin); freopen(file".out", "w", stdout); #define testinput(file) freopen(file".txt", "r", stdin); #define FAST_IO std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //#define PrintV(a) Fora(ii, a) cout << ii << ' '; cout << rl; //#define PrintVl(a) Fora(ii, a) cout << ii << rl; //#define PrintA(a, l, r) for (int ii = l; ii <= r; ii++) cout << a[ii] << ' '; cout << rl; //#define PrintAl(a, l, r) for (int ii = l; ii <= r; ii++) cout << a[ii] << rl; //#define Ptest(x) return cout << x, 0; #define setpre(n) fixed << setprecision(n) // pair #define F first #define S second #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<ld, ld> // vector & !!?(string) #define eb emplace_back #define pb push_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) a.size() #define len(a) a.length() // geometry calc #define pi acos(-1.0) #define g_sin(a) sin(a*pi/180) #define g_cos(a) cos(a*pi/180) #define g_tan(a) tan(a*pi/180) // set val #define ms0(a) memset(a, 0, sizeof(a)); #define ms1(a) memset(a, 1, sizeof(a)); #define msn1(a) memset(a, -1, sizeof(a)); #define msinf(a) memset(a, 0x3f3f3f, sizeof(a)); // constant const int mod1 = 998244353, mod = 1e9+7; const int MAXN = 1000005, MAXM = 200010; // code void Solve(){ ll n, p[60]; p[0] = 1; for (int i = 1; i < 60; ++ i) p[i] = p[i - 1] * 2ll; cin >> n; ll sum = 0, K = 0; while (true) { K ++; sum += p[K] + 3 * p[K] * (p[K] - 1); //cout << p[K] + (p[K] + p[K + 1]) * (p[K + 1] - p[K] - 1) << endl; //cout << pow(p[K + 1], 2) - pow(p[K], 2) - p[K + 1] << endl; if (sum >= n) break; } sum -= p[K] + 3 * p[K] * (p[K] - 1); n -= sum; //cout << n << endl; if (n <= p[K]) { if (n == p[K]) cout << "LOSE"; else cout << "WIN"; } else { n -= p[K]; ll l = 1, r = p[K] - 1; while (l < r) { ll mid = (l + r - 1) / 2; ll tmp = 2ll * (p[K] * mid + (mid + 1) * mid / 2); if (tmp >= n) r = mid; else l = mid + 1; } ll tmp = 2ll * (p[K] * (l - 1) + (l - 1) * l / 2); if (n == tmp + p[K] + l || n == tmp + p[K] * 2 + l * 2) cout << "LOSE"; else cout << "WIN"; } } signed main(){ freopen("nim.in", "r", stdin); freopen("nim.out", "w", stdout); FAST_IO; int TC = 1; //cin >> TC; while(TC--) Solve(); cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n"; return 0; }
Editor Settings
Theme
Key bindings
Full width
Lines