| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 550600 | Olympia | Cave (IOI13_cave) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <map>
#include <complex>
#include <cmath>
#include <set>
#include "cave.h"
using namespace std;
vector<bool> oracle = {true, true, false, true};
vector<int> door = {3, 1, 0, 2};
int n = 4;
int tryCombination(bool v[]) {
vector<int> doors;
for (int i = 0; i < n; i++) {
if (v[i] == oracle[i]) {
doors.push_back(door[i]);
}
}
sort(doors.begin(), doors.end());
for (int i = 0; i < doors.size(); i++) {
if (doors[i] != i) {
return i;
}
}
return doors.size();
}
vector<pair<int,bool>> vec;
void fill (bool v[]) {
for (auto& p: vec) {
v[p.first] = p.second;
}
}
/*
void exploreCave (int n) {
bool c[n]; int arr[n];
for (int i = 0; i < n; i++) {
vector<bool> a;
a.assign(n, true);
fill(a);
bool b = (tryCombination(a) >= i + 1);
int l = 0;
int r = n - 1;
while (l != r) {
int m = (l + r)/2;
a.assign(n, !b);
for (int j = 0; j <= m; j++) {
a[j] = b;
}
fill(a);
if (tryCombination(a) >= i + 1) {
r = m;
} else {
l = m + 1;
}
}
//cout << i << " " << l << '\n';
arr[l] = i;
vec.emplace_back(l, b);
}
answer(c, arr);
}
*/
void exploreCave (int N) {
assert(oracle.size() == door.size());
vector<bool> c; c.assign(n, false);
vector<int> arr; arr.assign(n, 0);
for (int i = 0; i < n; i++) {
bool a[n];
for (int j = 0; j < n; j++) a[j] = true;
fill(a);
bool b = (tryCombination(a) >= i + 1);
int l = 0;
int r = n - 1;
while (l != r) {
int m = (l + r)/2;
for (int j = 0; j < n; j++) a[j] = !b;
for (int j = 0; j <= m; j++) {
a[j] = b;
}
fill(a);
if (tryCombination(a) >= i + 1) {
r = m;
} else {
l = m + 1;
}
}
arr[l] = i;
vec.emplace_back(l, b);
}
for (auto& p: vec) {
c[p.first] = p.second;
}
answer(c, arr);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}