| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 635181 | marvinthang | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*************************************
* author: marvinthang *
* created: 25.08.2022 22:19:29 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
set <int> insides;
void add(int i) {
move_inside(i);
insides.insert(i);
}
void remove(int i) {
move_outside(i);
insides.erase(i);
}
void reset_machine(void) {
set <int> tmp = insides;
for (int i: tmp) remove(i);
}
int min_cardinality(int n) {
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > 1) remove(i);
}
int unique_vals = insides.size();
reset_machine();
int l = 2, r = n / unique_vals;
while (l <= r) {
int m = l + r >> 1;
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > mid) remove(i);
}
int total = insides.size();
reset_machine();
if (total >= unique_vals * mid) l = m + 1;
else r = m - 1;
}
return r;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
file("ioi22_day2_insects");
cerr << "Time elapsed: " << TIME << " s.\n";
return (0^0);
}