# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
605177 | Sam_a17 | 버섯 세기 (IOI20_mushrooms) | C++14 | 140 ms | 1556 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define pb push_back
#define ld long double
#define ll long long
// #include "mushrooms.h"
int use_machine(vector<int> m);
void pr(vector<int>& a) {
cerr << "arr" << " ";
for(auto i: a) {
cerr << i << " ";
} cerr << endl;
}
// #include "mushrooms.h"
int use_machine(vector<int> m);
int count_mushrooms(int n) {
set<int> st;
for(int i = 0; i < n; i++) {
st.insert(i);
}
int answ = 0;
int kAx = 1, kBx = 0, cnt = 0, qn = 0;
int lim = 80;
vector<int> ones, zeroes{0};
int start = -1;
for(int i = 1; i < n; i++) {
vector<int> aski{0, i};
int s = use_machine(aski);
if(s == 1) {
ones.push_back(i);
kBx++;
} else {
zeroes.push_back(i);
kAx++;
}
if(kAx >= 2 || kBx >= 2) {
start = i + 1;
break;
}
}
if(start == -1) {
return kAx;
}
if(kAx >= 2) {
for(int i = start; i + 1 < n; i += 2) {
vector<int> ask{0, i, zeroes.back(), i + 1};
int s = use_machine(ask);
if(s == 0) {
zeroes.push_back(i);
zeroes.push_back(i + 1);
} else if(s == 1) {
zeroes.push_back(i);
ones.push_back(i + 1);
} else if(s == 2) {
ones.push_back(i);
zeroes.push_back(i + 1);
} else {
ones.push_back(i);
ones.push_back(i + 1);
}
//
kAx = sz(zeroes), kBx = sz(ones);
if(kAx >= lim || kBx >= lim) {
start = i + 2;
break;
}
start += 2;
}
} else {
for(int i = start; i + 1 < n; i += 2) {
vector<int> ask{ones.front(), i, ones.back(), i + 1};
int s = use_machine(ask);
if(s == 0) {
ones.push_back(i);
ones.push_back(i + 1);
} else if(s == 1) {
ones.push_back(i);
zeroes.push_back(i + 1);
} else if(s == 2) {
zeroes.push_back(i);
ones.push_back(i + 1);
} else {
zeroes.push_back(i);
zeroes.push_back(i + 1);
}
//
kAx = sz(zeroes), kBx = sz(ones);
if(kAx >= lim || kBx >= lim) {
start = i + 2;
break;
}
start += 2;
}
}
// pr(zeroes);
// pr(ones);
// dbg(answ)
int countt = 0;
while(start < n) {
kAx = sz(zeroes), kBx = sz(ones);
// dbg(kAx)
// dbg(kBx)
if(kAx > kBx) {
vector<int> qry;
for(int j = start, k = 0; j < min(n, start + kAx); j++, k++) {
qry.push_back(zeroes[k]);
qry.push_back(j);
}
if(!qry.empty()) {
int s = use_machine(qry);
int ci = 0;
bool flag = false;
if(s % 2 == 1) {
s--, ci++;
ones.push_back(qry.back());
} else {
countt++;
zeroes.push_back(qry.back());
}
answ += (sz(qry) / 2 - ci) - (s / 2);
}
} else {
vector<int> qry;
for(int j = start, k = 0; j < min(n, start + kBx); j++, k++) {
qry.push_back(ones[k]);
qry.push_back(j);
}
if(!qry.empty()) {
int s = use_machine(qry);
pr(qry);
int ci = 0;
if(s % 2 == 1) {
s++, countt++;
zeroes.push_back(qry.back());
} else {
ones.push_back(qry.back());
}
// dbg(s)
answ += (s / 2);
}
}
start += max(kAx, kBx);
}
return answ + sz(zeroes) - countt;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |