제출 #594900

#제출 시각아이디문제언어결과실행 시간메모리
594900MadokaMagicaFan버섯 세기 (IOI20_mushrooms)C++14
10 / 100
233 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; return ans; } #ifdef ONPC vi rans; int use_machine(vi x){ 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; } int main() { freopen("in", "r", stdin); // ios_base::sync_with_stdio(0);cin.tie(0); solve(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...