Submission #1042786

#TimeUsernameProblemLanguageResultExecution timeMemory
1042786AmirAli_H1Counting Mushrooms (IOI20_mushrooms)C++17
0 / 100
1 ms344 KiB
// In the name of Allah #include <bits/stdc++.h> #include "mushrooms.h" using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 20000 + 4; const int M = 141; vector<int> ls[2], lsx; int col[maxn]; int count_mushrooms(int n) { int i = 0, T = 0; while (i < n) { if (i + 1 >= n || max(len(ls[0]), len(ls[1])) <= 1) { if (i == 0) col[i] = 0; else if (use_machine({0, i}) == 1) col[i] = 1; else col[i] = 0; T = 1; } else { int R = 0; if (len(ls[1]) >= len(ls[0])) R = 1; int x = use_machine({ls[R][0], i, ls[R][1], i + 1}); if (x == 0) col[i] = col[i + 1] = R; else if (x == 1) { col[i] = R; col[i + 1] = 1 - R; } else if (x == 2) { col[i] = 1 - R; col[i + 1] = R; } else col[i] = col[i + 1] = 1 - R; T = 2; } while (T--) { ls[col[i]].pb(i); i++; } if (max(len(ls[0]), len(ls[1])) >= M) break; } int res = len(ls[0]); if (n <= i) return res; while (i < n) { int R = 0; lsx.clear(); if (len(ls[1]) >= len(ls[0])) R = 1; int mx = max(len(ls[0]), len(ls[1])); for (int j = i; j < min(n, i + mx); j++) { lsx.pb(j); lsx.pb(ls[R][j - i]); } int x = use_machine(lsx); int t1 = (x + 1) / 2, t2 = (min(n, i + mx) - i) - t1; if (R == 1) res += t1; else res += t2; int j = min(n, i + mx) - 1; if (x % 2 == 1) col[j] = 1 - R; else col[j] = R; ls[col[j]].pb(j); i += mx; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...