| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 320693 | egod1537 | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int *arr, *con;
bitset<5001> vit;
//int tryCombination(int S[]) {
// for (int i = 0; i < n; i++)
// cout << S[i] << " ";
// cout << "\n";
//
// int ret; cin >> ret;
// return ret;
//}
void rev(int s, int e) {
for (int i = s; i <= e; i++) {
if (vit[i]) continue;
arr[i] = !arr[i];
}
}
void exploreCave(int _n) {
n = _n;
arr = new int[n];
con = new int[n];
memset(arr, 0, _msize(arr));
memset(con, 0, _msize(con));
for (int i = 0; i < n; i++) {
int lo = i, hi = n - 1;
int state = tryCombination(arr);
if (state == -1) state = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
rev(lo, mid);
int now = tryCombination(arr);
rev(lo, mid);
//case1 i번째 문이 닫혀 있는 경우
if (state == i) {
if (now > i) hi = mid - 1;
else lo = mid + 1;
}
//case2 i번째 문이 열려있는 경우
else if(state > i) {
if (now == i) hi = mid - 1;
else lo = mid + 1;
}
}
if (lo == n) lo = 0;
if (state == i) arr[lo] = !arr[lo];
//cout << "result : " << i << " " << lo << "\n";
con[lo] = i;
vit[lo] = true;
}
//for (int i = 0; i < n; i++)
// cout << arr[i] << " ";
//cout << "\n";
//for (int i = 0; i < n; i++)
// cout << con[i] << " ";
//cout << "\n";
answer(arr, con);
}
//
//int main() {
// exploreCave(4);
// return 0;
//}