Submission #69594

#	Time	Username	Problem	Language	Result	Execution time	Memory
69594		win11905	Martian DNA (IOI16_dna)	C++11	100 / 100	17 ms	1376 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

string analyse(int n, int t) {
    string str;
    srand(time(NULL));
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        str.push_back(rand() % 2 ? '1' : '0');
        if(make_test(str)) { cnt = 0; continue; }
        str.back() = str.back() == '1' ? '0' : '1'; 
        if(++cnt == 19 || i == n-1) {
            int l = 0, r = cnt;
            while(l < r) {
                int m = l + r>> 1;
                string ret;
                for(int j = 0; j <= i-m; ++j) ret.push_back(str[j]);
                if(make_test(ret)) r = m;
                else l = m+1;
            }
            string ret;
            for(int j = 0; j <= i-r; ++j) ret.push_back(str[j]);
            str = ret;
            break;
        }
    }
    while(str.size() != n) {
        str = (rand() % 2 ? "1" : "0") + str;
        if(make_test(str)) continue;
        str[0] = str[0] == '1' ? '0' : '1';
    }
    return str;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:16:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 int m = l + r>> 1;
                         ~~^~~
dna.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(str.size() != n) {
           ~~~~~~~~~~~^~~~
grader.cpp: In function 'bool make_test(std::__cxx11::string)':
grader.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) {
                  ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= ss.size(); i++) {
                  ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pr[i] == p.size()) {

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 64 / 64