#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include "dna.h"
using namespace std;
int N, T, len;
string makeStr(int size, char c = '0') {
string s = "";
for (int rep = 0; rep < size; ++rep) s.push_back(c);
return s;
}
bool endswith(string s, string suffix) {
// does s end with suffix;
if (s.size() < suffix.size()) return false;
while (!suffix.empty()) {
if (s.back() != suffix.back()) return false;
s.pop_back();
suffix.pop_back();
}
return true;
}
int maxLen() {
int l = 0, r = N + 1;
while (l + 1 < r) {
int m = (l + r) / 2;
if (make_test(makeStr(m))) l = m;
else r = m;
}
return l;
}
string extendRight(string curr) {
do {
if (make_test(curr + '1')) {
curr.push_back('1');
}
else {
// assume its a 0, even though it might be the end of the string
curr.push_back('0');
}
} while (!endswith(curr, makeStr(len + 1)));
return curr;
}
string cullRight(string curr) {
int l = curr.size() - len - 1, r = curr.size() + 1;
while (l + 1 < r) {
int m = (l + r) / 2;
if (make_test(curr.substr(0, m))) l = m;
else r = m;
}
return curr.substr(0, l);
}
string extendLeft(string curr) {
while (curr.size() < N) {
if (make_test('1' + curr)) {
curr = '1' + curr;
}
else {
// assume its a 0, even though it might be the end of the string
curr = '0' + curr;
}
}
return curr;
}
string analyse(int n, int t) {
N = n;
T = t;
len = maxLen();
if (len == 0) return makeStr(N, '1');
string curr = makeStr(len);
//cout << curr << "\n";
curr = extendRight(curr);
//cout << curr << "\n";
curr = cullRight(curr);
//cout << curr << "\n";
curr = extendLeft(curr);
//cout << curr << "\n";
return curr;
}
/*int main() {
if (ans != analyse(ans.size(), -1)) throw 20;
cout << numTests;
}*/
Compilation message
dna.cpp: In function 'std::string extendLeft(std::string)':
dna.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | while (curr.size() < N) {
| ~~~~~~~~~~~~^~~
grader.cpp: In function 'bool make_test(std::string)':
grader.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 1; i <= ss.size(); i++) {
| ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (pr[i] == p.size()) {
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
292 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
292 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
292 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
292 KB |
Output is correct |
| 14 |
Correct |
1 ms |
252 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
288 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| 34 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
296 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
288 KB |
Output is correct |
| 22 |
Correct |
11 ms |
292 KB |
Output is correct |
| 23 |
Correct |
11 ms |
288 KB |
Output is correct |
| 24 |
Correct |
10 ms |
332 KB |
Output is correct |
| 25 |
Correct |
14 ms |
332 KB |
Output is correct |
| 26 |
Correct |
13 ms |
364 KB |
Output is correct |
| 27 |
Correct |
7 ms |
288 KB |
Output is correct |
| 28 |
Correct |
8 ms |
372 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
6 ms |
388 KB |
Output is correct |
| 32 |
Correct |
1 ms |
204 KB |
Output is correct |
| 33 |
Correct |
9 ms |
372 KB |
Output is correct |
| 34 |
Correct |
10 ms |
332 KB |
Output is correct |
| 35 |
Correct |
8 ms |
292 KB |
Output is correct |
| 36 |
Correct |
8 ms |
332 KB |
Output is correct |
| 37 |
Correct |
8 ms |
332 KB |
Output is correct |
| 38 |
Correct |
16 ms |
356 KB |
Output is correct |
| 39 |
Correct |
6 ms |
292 KB |
Output is correct |
