Submission #69873

#	Time	Username	Problem	Language	Result	Execution time	Memory
69873		aquablitz11	Martian DNA (IOI16_dna)	C++14	100 / 100	18 ms	764 KiB

dna

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

inline string rep(char c, int n) {
    assert(c == '0' || c == '1');
    string ret;
    for (int i = 0; i < n; ++i)
        ret.push_back(c);
    return ret;
}

string analyse(int n, int t)
{
    int b = 0, e = n;
    while (b < e) {
        int m = (b+e+1)/2;
        if (make_test(rep('0', m))) b = m;
        else e = m-1;
    }
    int max0len = e;
    if (max0len == n) return rep('0', n);
    if (max0len == 0) return rep('1', n);
    string str = rep('0', max0len);
    if (make_test(str+'1')) {
        str.push_back('1');
        while (true) {
            bool ok = false;
            for (int i = 0; i <= max0len && str.size()+i+1 <= n; ++i) {
                string q = str + rep('0', i) + '1';
                if (make_test(q)) {
                    str = q;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                int b = 0, e = max0len;
                while (b < e) {
                    int m = (b+e+1)/2;
                    string q = str + rep('0', m);
                    if (make_test(q)) b = m;
                    else e = m-1;
                }
                str += rep('0', b);
                break;
            }
        }
    }
    while (str.size() < n) {
        str = "0" + str;
        if (!make_test(str))
            str[0] = str[0]=='0' ? '1' : '0';
    }

    return str;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:29:60: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i <= max0len && str.size()+i+1 <= n; ++i) {
                                             ~~~~~~~~~~~~~~~^~~~
dna.cpp:50:23: 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