제출 #531145

#제출 시각아이디문제언어결과실행 시간메모리
531145ColourAttila버섯 세기 (IOI20_mushrooms)C++17
92.24 / 100
9 ms360 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; using ll = long long; const int maxN = 2e5 + 5; const int MOD = 1e9 + 7; vector<int> knownA , knownB, ask; int cnt; int query1(vector<int> a) { int res = use_machine(a); if(res == 1) { knownB.push_back(a.back()); } else { knownA.push_back(a.back()); } return res; } int query2(vector<int> a, bool type) { int res = use_machine(a); //cout << "type: " << type << endl; if(((res & 2) == 2) == type) { knownB.push_back(a[1]); } else { knownA.push_back(a[1]); } if(((res & 1) == 1) == type) { knownB.push_back(a.back()); } else { knownA.push_back(a.back()); } return res; } int query3(vector<int> a, bool type) { int res = use_machine(a); if(type) { cnt += (a.size() - res) / 2; if(!(res % 2)) knownA.push_back(a.back()); else knownB.push_back(a.back()); } else { cnt += (res + 1) / 2; if(res % 2) knownA.push_back(a.back()); else knownB.push_back(a.back()); } return res; } int count_mushrooms(int n){ knownA.push_back(0); if (n<220) { for (int i=1; i<n; i++) { ask = {0, i}; query1(ask); } return knownA.size(); } ask = {0, 1}; int curr = 1; // van legalabb 2 int res = query1(ask); if(res == 1) { if(n == 2) return 1; ask[1] = 2; query1(ask); curr++; } if(n == curr+1) return knownA.size(); int sq = sqrt(n)/2; //gyöknyi ugyanolyan keresese while((int)knownA.size() < sq && (int)knownB.size() < sq) { ask.clear(); bool type; if(knownA.size() > 1) { ask = {knownA[0], ++curr, knownA[1], ++curr}; type = 1; } else { ask = {knownB[0], ++curr, knownB[1], ++curr}; type = 0; } query2(ask, type); } // megoldas cnt = knownA.size(); while(curr < n-1) { ask.clear(); bool type; if(knownA.size() > knownB.size()) { type = 1; for(int i = 0; i < (int)knownA.size(); i++) { ask.push_back(knownA[i]); ask.push_back(++curr); if(curr == n-1) break; } } else { type = 0; for(int i = 0; i < (int)knownB.size(); i++) { ask.push_back(knownB[i]); ask.push_back(++curr); if(curr == n-1) break; } } query3(ask, type); } return cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...