| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1333358 | horiaboeriu | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cave.h"
#include "grader.h"
using namespace std;
const int MAXN = 5000;
int s[MAXN], v[MAXN], d[MAXN];
void exploreCave(int n) {
int i, j, x, rez, st, dr, mij, nr;
//O(n^2 * log(n))
//o sa o fac din N * logN + N cred adica <= 70 de mii
//ca mai intai pentru usa i voi face un query ca sa vad daca trebuie sa fie in sus sau in joc s2withcul ca sa se deschida
//si dupa tot injumatatesc candidatii ca pe primii ii pun in jos si pe restul in sus deci din log queryuri aflu care switch este la acea usa
for (i = 0; i < n; i++) {
d[i] = -1;//nu stiu inca ce usa are
}
for (i = 0; i < n; i++) {
//le testez normal pe cele de la 0 la i - 1 cat sa se deschida si le pun 1 la restul, insemnand ca e in jos switchul
for (j = 0; j < n; j++) {
v[j] = s[j];
if (d[j] < 0) {
v[j] = 1;//in jos
}
}
x = tryCombination(v);
rez = 0;
if (x != i) {
rez = 1;//este in jos maneta
}
st = 0;
dr = n - i;
while (dr - st > 1) {
mij = (st + dr) / 2;
//primele mij sunt cu rez si ultimele cu rez ^ 1
nr = mij;
for (j = 0; j < n; j++) {
v[j] = s[j];
if (d[j] < 0) {
if (nr > 0) {
v[j] = rez;
nr--;
} else {
v[j] = (rez ^ 1);
}
}
}
x = tryCombination(v);
if (x == i) {
st = mij;//am incercat prea putine switchuri din prefix cu rez
} else {
dr = mij;
}
}
//il caut pe al dr-lea
j = 0;
while (dr > 0) {
if (d[j] < 0) {
dr--;
}
j++;
}
j--;//acesta este switchul
d[j] = i;
s[j] = rez;
}
answer(s, d);
}