# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527970 | tabr | Martian DNA (IOI16_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
function<bool(string)> make_test;
#else
#include "dna.h"
#endif
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int rand_int(int a, int b) { // [a, b]
return uniform_int_distribution<int>(a, b)(rng);
}
string analyse(int n, int) {
string ans;
int lst = -1;
for (int i = 0; i < n; i++) {
string c = to_string(rand_int(0, 1));
if (make_test(ans + c)) {
ans += c;
lst = i;
} else {
ans += to_string(c[0] ^ '0' ^ '1');
}
if (lst + 15 < i) {
if (make_test(ans)) {
lst = i;
continue;
}
int low = lst + 1;
int high = (int) ans.size();
while (high - low > 1) {
int mid = (high + low) >> 1;
if (make_test(ans.substr(mid)) {
low = mid;
} else {
high = mid;
}
}
ans.resize(low);
lst = low - 1;
break;
}
}
for (int i = (int) ans.size(); i < n; i++) {
string c = to_string(rand_int(0, 1));
if (make_test(c + ans)) {
ans = c + ans;
} else {
ans = c + ans;
}
}
return ans;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
#endif