| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 592821 |
2022-07-09T16:14:47 Z |
tarche |
Martian DNA (IOI16_dna) |
C++17 |
|
13 ms |
388 KB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int lengthLongestZeroChain(int n) {
int low = 0, high = n;
while (low + 1 < high) {
int mid = (low + high) / 2;
string s(mid, '0');
if (make_test(s)) {
low = mid;
} else {
high = mid;
}
}
return low;
}
void findStringEnding(string& s, string& chain) {
int n = (int)chain.length();
int low = 0, high = n;
while (low + 1 < high) {
int mid = (low + high) / 2;
chain = string(mid, '0');
if (make_test(s + chain)) {
low = mid;
} else {
high = mid;
}
}
s += string(low, '0');
}
void growSubstringRight(string& s, string& chain) {
if (make_test(s + chain + '1')) {
s += chain + '1';
chain = "";
} else {
chain += '0';
}
}
void growSubstringLeft(string& s) {
if (make_test('1' + s)) {
s = "1" + s;
} else {
s = "0" + s;
}
}
string analyse(int n, int t) {
int zeroChainLen = lengthLongestZeroChain(n);
string curr(zeroChainLen, '0'), chain = "";
while ((int)chain.length() < zeroChainLen && (int)curr.length() < n) {
growSubstringRight(curr, chain);
}
if ((int)chain.length() == zeroChainLen) {
findStringEnding(curr, chain);
}
while ((int)curr.length() < n) {
growSubstringLeft(curr);
}
return curr;
}
Compilation message
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()) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
304 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
308 KB |
Wrong DNA |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
212 KB |
Wrong DNA |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
304 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 19 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Incorrect |
0 ms |
212 KB |
Wrong DNA |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 30 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 31 |
Incorrect |
1 ms |
212 KB |
Wrong DNA |
| 32 |
Correct |
1 ms |
308 KB |
Output is correct |
| 33 |
Correct |
1 ms |
304 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
300 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
300 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
308 KB |
Wrong DNA |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
300 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
304 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
308 KB |
Output is correct |
| 19 |
Correct |
1 ms |
296 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
300 KB |
Wrong DNA |
| 22 |
Correct |
8 ms |
304 KB |
Output is correct |
| 23 |
Incorrect |
9 ms |
364 KB |
Wrong DNA |
| 24 |
Incorrect |
9 ms |
304 KB |
Wrong DNA |
| 25 |
Correct |
12 ms |
364 KB |
Output is correct |
| 26 |
Correct |
13 ms |
340 KB |
Output is correct |
| 27 |
Correct |
6 ms |
352 KB |
Output is correct |
| 28 |
Incorrect |
7 ms |
388 KB |
Wrong DNA |
| 29 |
Correct |
12 ms |
340 KB |
Output is correct |
| 30 |
Correct |
6 ms |
308 KB |
Output is correct |
| 31 |
Correct |
5 ms |
340 KB |
Output is correct |
| 32 |
Correct |
12 ms |
304 KB |
Output is correct |
| 33 |
Correct |
8 ms |
304 KB |
Output is correct |
| 34 |
Correct |
8 ms |
340 KB |
Output is correct |
| 35 |
Correct |
7 ms |
340 KB |
Output is correct |
| 36 |
Incorrect |
7 ms |
340 KB |
Wrong DNA |
| 37 |
Incorrect |
7 ms |
308 KB |
Wrong DNA |
| 38 |
Correct |
4 ms |
340 KB |
Output is correct |
| 39 |
Correct |
9 ms |
352 KB |
Output is correct |
