Submission #724908

#TimeUsernameProblemLanguageResultExecution timeMemory
724908MohamedAliSaidaneCounting Mushrooms (IOI20_mushrooms)C++14
92.62 / 100
10 ms440 KiB
#include<bits/stdc++.h> #include "mushrooms.h" #include<ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int,int> pii; typedef vector<pii> vpi; #define ff first #define ss second #define pb push_back #define all(x) (x).begin(),(x).end() const ll MOD = 1e9 + 7, INF = 1e18; ll mod(ll x, ll m = MOD) {return (x + m) % m;} int N; string S; /* int use_machine(vi v) { int rep = 0; for(int i = 0; i < (int)(v.size()) - 1; i++) rep += (S[v[i]] != S[v[i + 1]]); return rep; } */ int count_mushrooms(int n) { char c = 'A', d= 'B'; int a = 0, b = 1; int u = use_machine({0, 1}); if(n == 2) return 2 - u; int last = 1; if(u == 1) { last = 2; if(use_machine({0, 2})) { a= 2; swap(c, d); } else b = 2; } vi A = {a, b}; vi B; for(int j = 0; j <= last; j++) if(j != a && j != b) B.pb(j); int sza = (int)(A.size()), szb = (int)(B.size()); int SQ = 85; for(int i = last + 1; max(sza, szb) < SQ && max(sza, szb) * max(sza, szb) < n; i+= 2) { if(i == n -1) { last = i; if(use_machine({a, i})) B.pb(i); else A.pb(i); } else { last = i + 1; u = use_machine({a, i, b, i + 1}); if(u == 1) { A.pb(i); B.pb(i + 1); } else if(u == 0) { A.pb(i); A.pb(i + 1); } else if(u == 2) { A.pb(i + 1); B.pb(i); } else { B.pb(i); B.pb(i + 1); } } sza = (int)(A.size()); szb = (int)(B.size()); } if(sza < szb) { swap(c, d); swap(A, B); swap(sza, szb); } int cnt = szb; int flag = 0; int Bloc = sza; for(int j = last + 1; j < n; j += Bloc) { vi v; Bloc = min(n - j, sza); for(int k = 0; k < Bloc; k++) { v.pb(A[k]); v.pb(j + k); } int r = use_machine(v); cnt += (r + 1)/2; if(r & 1) B.pb(j + Bloc - 1); else A.pb(j + Bloc - 1); sza = (int)(A.size()); szb = (int)(B.size()); if(szb > sza) { swap(sza, szb); swap(A, B); swap(c, d); cnt = j + Bloc - cnt; } } if(c == 'B') return cnt; else return n - cnt; } /* int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; cin >> S; cout << count_mushrooms(N); } */

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:104:9: warning: unused variable 'flag' [-Wunused-variable]
  104 |     int flag = 0;
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...