# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
423238 | xyz | 버섯 세기 (IOI20_mushrooms) | C++17 | 16 ms | 344 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef long long ll;
int m = 50;
int count_mushrooms(int n){
vector<int> A, B;
A = {0};
int go = 2 * m + 5;
for(int i = 1; i < min(n, go); i ++){
vector<int> ask = {0, i};
int x = use_machine(ask);
if(!x)
A.push_back(i);
else
B.push_back(i);
}
// for(int x : A)
// cout << x << " ";
// cout << endl;
// for(int x : B)
// cout << x << " ";
// cout << endl;
int result = A.size(), pos = go;
while(pos < n){
m = max((int)A.size(), (int)B.size()) - 1;
if(A.size() >= B.size()){
vector<int> ask;
if(pos + m < n)
ask.push_back(pos + m);
ask.push_back(A[0]);
int cur = 1;
for(int j = pos; j < min(n, pos + m); j ++){
ask.push_back(j);
ask.push_back(A[cur]);
++ cur;
}
// cout << "-query1" << endl;
// cout << ask.size() << endl;
// for(int e : ask)
// cout << e << " ";
// cout << endl;
int x = use_machine(ask), y = ask.size();
// cout << "reply = " << x << endl;
if(pos + m < n){
-- y;
if(x % 2 == 1){
B.push_back(pos + m);
-- x;
}else{
A.push_back(pos + m);
++ result;
}
}
result += ((y - 1) - x) / 2;
pos += m + 1;
}else{
vector<int> ask;
if(pos + m < n)
ask.push_back(pos + m);
ask.push_back(B[0]);
int cur = 1;
for(int j = pos; j < min(n, pos + m); j ++){
ask.push_back(j);
ask.push_back(B[cur]);
++ cur;
}
// cout << "-query2" << endl;
// cout << ask.size() << endl;
// for(int e : ask)
// cout << e << " ";
// cout << endl;
int x = use_machine(ask);
// cout << "reply = " << x << endl;
if(pos + m < n){
if(x % 2 == 1){
A.push_back(pos + m);
++ result;
-- x;
}else{
B.push_back(pos + m);
}
}
result += x / 2;
pos += m + 1;
}
}
return result;
}
//23
//0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0
//answer : 17
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |