| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 208558 | teomrn | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
#define local1
#ifdef local
int _n;
int _ans[1000];
int _coresp[1000]; /// coresp[i] = ce actioneaza fiecare switch
int tryCombination(int S[])
{
int best = 1e9;
for (int i = 0; i < _n; i++)
if (S[i] != _ans[i])
best = min(best, _coresp[i]);
return (best == 1e9 ? -1 : best);
}
void answer(int S[], int D[])
{
for (int i = 0; i < _n; i++) {
if (S[i] != _ans[i])
cerr << "Bad for i = " << i << " and S\n";
if (D[i] != _coresp[i])
cerr << "Bad for i = " << i << " and D\n";
}
}
#endif
void exploreCave(int N)
{
vector <int> switches(N);
iota(switches.begin(), switches.end(), 0);
vector <int> ans(N), coresp(N);
vector <int> question(N);
for (int door = 0; door < N; door++) {
// vreau sa deschid usa door
int value = 0;
for (auto i : switches)
question[i] = 0;
int guess = tryCombination(question.data());
if (guess <= door && guess != -1)
value = 1; /// usa o sa se deschida cu switch-ul pe 1
int p = -1;
for (int q = (1 << 20); q; q /= 2) {
if (p + q < switches.size() - 1) {
int val = p + q;
for (int i = 0; i <= val; i++)
question[switches[i]] = 1 - value;
for (int i = val + 1; i < (int)switches.size(); i++)
question[switches[i]] = value;
int guess = tryCombination(question.data());
for (auto i : question)
cerr << i << ' ';
if (guess > door || guess == -1)
p += q;
}
}
p = switches[p + 1];
/// usa door este actionata de switch-ul p
coresp[p] = door;
ans[p] = value;
question[p] = value;
switches.erase(find(switches.begin(), switches.end(), p));
}
answer(ans.data(), coresp.data());
}
#ifdef local
int main()
{
ifstream cin("input.in");
cin >> _n;
for (int i = 0; i < _n; i++)
cin >> _ans[i];
for (int i = 0; i < _n; i++)
cin >> _coresp[i];
exploreCave(_n);
return 0;
}
#endif