이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include <bits/stdc++.h>
#define R(a) for (int i = 0; i < a; ++i)
#define RR(a) for (int j = 0; j < a; ++j)
using namespace std;
bool testDoor(int swit[], int door)
{
int res = tryCombination(swit);
if (door < res || res == -1) return true;
else return false;
}
void exploreCave(int N) {
int sPoses[N];
int switchStates[N];
int doorStates[N];
R(N)
{
sPoses[i] = -1;
switchStates[i] = -1;
doorStates[i] = -1;
}
R(N)
{
bool zero = false;
if (doorStates[i] == -1)
{
int initialTestSwitches[N];
RR(N)
{
if (switchStates[j] == -1) initialTestSwitches[j] = 0;
else initialTestSwitches[j] = switchStates[j];
}
int res = tryCombination(initialTestSwitches);
if (res == -1)
{
zero = true;
for (int j = i; j < N; ++j)
{
doorStates[j] = 0;
}
}
else if (i < res)
{
zero = true;
for (int j = i; j < res; ++j)
{
doorStates[j] = 0;
}
}
}
else zero = true;
if (zero)
{
int lower = 0;
int upper = N - 1;
int definite = -1;
while (upper - lower > 1)
{
int mid = (lower + upper) / 2;
int testSwitches[N];
RR(N)
{
if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
else
{
if (lower <= j && j <= mid) testSwitches[j] = 0;
else testSwitches[j] = 1;
}
}
if (testDoor(testSwitches, i))
{
upper = mid;
}
else
{
lower = mid;
if (lower + 1 == upper) definite = upper;
}
}
if (definite > -1)
{
sPoses[i] = definite;
switchStates[definite] = 0;
}
else
{
int testSwitches[N];
RR(N)
{
if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
else
{
if (j == lower) testSwitches[j] = 0;
else testSwitches[j] = 1;
}
}
if (testDoor(testSwitches, i))
{
sPoses[i] = lower;
switchStates[lower] = 0;
}
else
{
sPoses[i] = upper;
switchStates[upper] = 0;
}
}
}
else
{
int lower = 0;
int upper = N - 1;
int definite = -1;
while (upper - lower > 1)
{
int mid = (lower + upper) / 2;
int testSwitches[N];
RR(N)
{
if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
else
{
if (lower <= j && j <= mid) testSwitches[j] = 1;
else testSwitches[j] = 0;
}
}
if (testDoor(testSwitches, i))
{
upper = mid;
}
else
{
lower = mid;
if (lower + 1 == upper) definite = upper;
}
}
if (definite > -1)
{
sPoses[i] = definite;
switchStates[definite] = 1;
}
else
{
int testSwitches[N];
RR(N)
{
if (switchStates[j] != -1) testSwitches[j] = switchStates[j];
else
{
if (j == lower) testSwitches[j] = 1;
else testSwitches[j] = 0;
}
}
if (testDoor(testSwitches, i))
{
sPoses[i] = lower;
switchStates[lower] = 1;
}
else
{
sPoses[i] = upper;
switchStates[upper] = 1;
}
}
}
}
int switchesForDoors[N];
R(N)
{
switchesForDoors[sPoses[i]] = i;
}
/*R(N)
{
cout << switchesForDoors[i] << " ";
}
cout << endl;
R(N)
{
cout << switchStates[i] << " ";
}
cout << endl;*/
answer(switchStates, switchesForDoors);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |