#include "cave.h"
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
set<int> use;
int n;
//vector<int> sa, da;
//int tryCombination(int s[]) {
// int ans = -1;
// for (int i = 0; i < n; i++) printf("%d ", s[i]);
// for (int i = 0; i < n; i++) {
// if (s[i] != sa[i]) {
// ans = i;
// break;
// }
// }
// printf(" -> %d\n", ans);
// return ans;
//}
pair<int, int> bsearch(int i, int s[]) {
vector<int> t;
for (auto u: use) t.push_back(u);
int cntrl = tryCombination(s);
if (cntrl == -1) cntrl = n+2;
int l = 0, r = t.size()-1;
while(l < r) {
int m = (l + r) / 2;
int ts[n];
for (int i = 0; i < n; i++) ts[i] = s[i];
for (int i = l; i <= m; i++) {
ts[t[i]] = 1-ts[t[i]];
}
int ans = tryCombination(ts);
if (ans == -1) ans = n + 2;
if (cntrl == i && ans > i) r = m;
else if (cntrl > i && ans == i) r = m;
else l = m + 1;
}
// the switch is t[l]
int corpos;
if (cntrl > i) corpos = s[t[l]];
else corpos = 1 - s[t[l]];
return {t[l], corpos};
}
void exploreCave(int N) {
n = N;
int s[n], d[n];
for (int i = 0; i < n; i++) s[i] = 0;
for (int i = 0; i < n; i++) use.insert(i);
for (int i = 0; i < n; i++) {
pair<int, int> ans = bsearch(i, s);
use.erase(ans.first);
s[ans.first] = ans.second;
d[ans.first] = i;
}
answer(s, d);
//for (int i = 0; i < n; i++) printf("%d ", s[i]);
//printf("\n");
//for (int i = 0; i < n; i++) printf("%d ", d[i]);
//printf("\n");
}
//int main() {
// int t;
// scanf("%d", &t);
// sa.resize(t);
// da.resize(t);
// for (int i = 0; i < t; i++) {
// scanf("%d%d", &sa[i], &da[i]);
// }
// exploreCave(t);
//}
# | 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... |