Submission #824755

#TimeUsernameProblemLanguageResultExecution timeMemory
824755fatemetmhrCounting Mushrooms (IOI20_mushrooms)C++17
80.43 / 100
7 ms312 KiB
// Be name khoda // #include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << "(" << #x << "):" << x << endl; #define all(x) x.begin(), x.end(); #define fi first #define se second #define pb push_back #define mp make_pair const int ssq = 141; const int maxn5 = 1e5 + 10; vector <int> av, av2; int cnt[2], ty[maxn5]; int count_mushrooms(int n){ av = {0, 1}; int a = use_machine(av); ty[0] = 0; ty[1] = a; if(n == 2){ if(a) return 1; return 2; } av = {0, 2}; int b = use_machine(av); ty[2] = b; int x1, x2; if(a == 0){ x1 = 0; x2 = 1; } else if(b == 0){ x1 = 0; x2 = 2; } else{ x1 = 1; x2 = 2; } //cout << x1 << ' ' << x2 << endl; cnt[0] = 1 + (1 ^ ty[2]) + (1 ^ ty[1]); cnt[1] = ty[2] + ty[1]; int pt = 3; while(max(cnt[0], cnt[1]) < ssq && cnt[0] + cnt[1] < n){ if(pt + 1 == n){ av = {x1, pt}; int x = use_machine(av); ty[pt] = (ty[x1] ^ x); cnt[ty[pt]]++; pt++; continue; } av = {x1, pt, x2, pt + 1}; int x = use_machine(av); if(x == 0){ ty[pt] = ty[pt + 1] = ty[x1]; cnt[ty[x1]] += 2; } if(x == 1){ ty[pt] = ty[x1]; ty[pt + 1] = ty[x1] ^ 1; cnt[ty[x1]]++; cnt[ty[x1] ^ 1]++; } if(x == 2){ ty[pt] = ty[x1] ^ 1; ty[pt + 1] = ty[x1]; cnt[ty[x1]]++; cnt[ty[x1] ^ 1]++; } if(x == 3){ ty[pt] = ty[pt + 1] = ty[x1] ^ 1; cnt[ty[x1] ^ 1] += 2; } pt += 2; } if(cnt[0] + cnt[1] == n) return cnt[0]; int g = 0; if(cnt[1] > cnt[0]) g = 1; for(int i = 0; i < pt; i++) if(ty[i] == g) av2.pb(i); //cout << pt << ' ' << g << ' ' << av2.size() << endl; while(pt < n){ av.clear(); int ind = 0; while(pt < n && ind < av2.size()){ av.pb(av2[ind++]); av.pb(pt++); } int x = use_machine(av); int num = x / 2 + x % 2; cnt[g ^ 1] += num; cnt[g] += int(av.size()) / 2 - num; } return cnt[0]; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   while(pt < n && ind < av2.size()){
      |                   ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...