# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000012 | esomer | Martian DNA (IOI16_dna) | C++17 | 7 ms | 444 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;
bool make_test(string T);
string buildZeros(int zeros){
string s = "";
for(int i = 0; i < zeros; i++) s += '0';
return s;
}
string analyse(int N, int maxT) {
int maxZeroes = 0;
int lo = 1;
int hi = N;
while(lo <= hi){
int mid = (lo + hi) / 2;
string s = buildZeros(mid);
if(make_test(s)){
maxZeroes = mid;
lo = mid + 1;
}else hi = mid - 1;
}
string suf = buildZeros(maxZeroes);
int t = 0;
while(t <= maxZeroes){
suf += '1';
if(!make_test(suf)){
t++;
suf.pop_back();
suf += '0';
}else t = 0;
}
//I binary search to find exactly the suffix.
lo = 1;
hi = maxZeroes+1; //How many do I erase.
string nwSuf = suf;
while(lo <= hi){
int mid = (lo + hi) / 2;
string s = suf;
for(int i = 0; i < mid; i++) s.pop_back();
if(make_test(s)){
//This is suffix. I can erase less.
nwSuf = s;
hi = mid - 1;
}else lo = mid + 1;
}
suf = nwSuf;
//Now suf is exactly the suffix.
while((int)suf.size() < N){
reverse(suf.begin(), suf.end());
suf += '1';
reverse(suf.begin(), suf.end());
if(!make_test(suf)){
reverse(suf.begin(), suf.end());
suf.pop_back();
suf += '0';
reverse(suf.begin(), suf.end());
}
}
return suf;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |