Submission #594913

#TimeUsernameProblemLanguageResultExecution timeMemory
594913MadokaMagicaFanCounting Mushrooms (IOI20_mushrooms)C++14
25 / 100
118 ms464 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define all(v) v.begin(),v.end() #define sort(v) sort(all(v)) #define endl '\n' #define forn(i,n) for(int i = 0; i < n; ++i) #define forbe(i,b,e) for(int i = b; i < e; ++i) #define forr(i,n) for(int i = n-1; i >= 0; --i) #define sz(v) ((int)v.size()) #define pb push_back #define f first #define s second int use_machine(vi x); int count_mushrooms(int n) { vi type(n, 1); vi s(n,1); type[0] = 1; // while (s[0] < n) { // for (int i = 0; i < n;) { // assert(i+s[i] <= n); // if (i + s[i] == n) // break; // // if (use_machine({i, i + s[i]})) { // forbe(j, i+s[i], i+s[i]+s[i+s[i]]) // type[j] = 1 - type[j]; // } // // s[i] += s[i+s[i]]; // // i += s[i]; // } // } int ans = 0; // forn(i, n) // ans += type[i]; // forn(i, n) // cout << type[i] << ' '; // cout << endl; for(int i = 2; i < n; i+=2) { ans += 2 - use_machine({i, 0, i-1}); } if ((n&1)==0) ans += 1 - use_machine({n-1,0}); return ans+1; } #ifdef ONPC vi rans; int cnt = 0; int use_machine(vi x){ ++ cnt; int _ans = 0; forn(i , sz(x)-1) if (rans[x[i]] != rans[x[i+1]]) ++_ans; return _ans; } void solve() { int n; cin >> n; rans.resize(n); char c; forn(i, n) { cin >> c; rans[i]=(c=='A'); } cout << count_mushrooms(n) << endl; cout << n << cnt << endl; } int main() { // freopen("in", "r", stdin); // ios_base::sync_with_stdio(0);cin.tie(0); solve(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...