제출 #308690

#제출 시각아이디문제언어결과실행 시간메모리
308690M4mou버섯 세기 (IOI20_mushrooms)C++17
92.24 / 100
9 ms500 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define fi first #define se second #define inf 1000000000 #define sz(x) (ll)x.size() #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) typedef long long ll; typedef unsigned long long ull; typedef double ld; typedef vector<int> vi; typedef pair<int,int> pii; typedef pair< int , pii> piii; typedef pair<int,bool> pib; typedef vector<pii> vii; typedef vector<pib> vib; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<string> vs; typedef vector<ll> vll; typedef pair<string,string> pss; typedef vector<pss> vss; typedef pair<ld , ld> pdd; typedef vector<ld> vd; typedef vector<vector<pib>> vvib; typedef vector<piii> viii; typedef vector<viii> vviii; typedef vector<bool> vb; typedef pair<pii , bool> piib; typedef vector<pair<pii , bool>> viib; const int MOD = 1e9 + 7; //998244353; const int MAXN = 100005; string test = "AABABABABAA"; /* int use_machine(vi a){ int c = 0; for(int i = 0 ;i<a.size()-1;i++){ if(test[a[i]] != test[a[i+1]])c++; } return c; } */ vi a, b; int count_mushrooms(int n) { if(n < 226){ int c = 1; for(int i = 1;i<n;i++){ c += 1 - use_machine({0 , i}); } return c; } int k = 180; a.pb(0); for(int i = 1;i<=2;i++){ if(use_machine({0, i}) == 1)b.pb(i); else a.pb(i); } int co = 3; while(co <= k){ if(a.size() >= 2){ int x = use_machine({a[0], co , a[1] , co + 1}); if(x == 0){ a.pb(co); a.pb(co+1); } if(x == 1){ a.pb(co); b.pb(co+1); } if(x == 2){ b.pb(co); a.pb(co+1); } if(x == 3){ b.pb(co); b.pb(co+1); } } else { int x = use_machine({b[0], co , b[1] , co + 1}); if(x == 0){ b.pb(co); b.pb(co+1); } if(x == 1){ b.pb(co); a.pb(co+1); } if(x == 2){ a.pb(co); b.pb(co+1); } if(x == 3){ a.pb(co); a.pb(co+1); } } co += 2; } int score = 0; while(co < n){ vi query; if(a.size() > b.size()){ for(int i : a){ query.pb(i); query.pb(co); co++; if(co == n)break; } int x = use_machine(query); if(x&1){ b.pb(query.back()); x--; } else a.pb(query.back()); score += ((int)query.size() - x - 1)/2; } else { for(int i : b){ query.pb(i); query.pb(co); co++; if(co == n)break; } int x = use_machine(query); if(x&1){ a.pb(query.back()); x--; } else b.pb(query.back()); score += x/2; } } return score + a.size(); } /* int main(){ cout << count_mushrooms(test.size()) << endl; } */ //NEVER GIVE UP //LONG LONG
#Verdict Execution timeMemoryGrader output
Fetching results...