Submission #33852

#	Time	Username	Problem	Language	Result	Execution time	Memory
33852		nickyrio	Martian DNA (IOI16_dna)	C++14	100 / 100	13 ms	2020 KiB

dna

#include "dna.h"

#include <cstdlib>

using namespace std;

string add(string st, char c, int len) {
    for (int i = 0; i<len; i++) st.push_back(c);
    return st;
}

string analyse(int n, int t) {
    string now;
    now.clear();
    int l = 1;
    int r = n;
    int cur = 0;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (make_test(add(now, '1', m))) {
            cur = m;
            l = m + 1;
        } else r = m - 1;
    }
    if (cur == 0) return add(now, '0', n);
    now = add(now, '1', cur);
    int cnt = 0;
    while (cnt <= cur) {
        if (make_test(now + '0')) {
            cnt = 0;now.push_back('0');
        }
        else {
            cnt++; now.push_back('1');
        }
    }
    int suffix = cur;
    l = cur + 1;
    r = now.size();
    while (l <= r) {
        int m = (l + r) >> 1;
        if (make_test(now.substr(0, m))) {
            suffix = m;
            l = m + 1;
        } else r = m - 1;
    }
    now = now.substr(0, suffix);
    while (now.size() < n) {
        if (make_test('1' + now)) now = '1' + now;
        else now = '0' + now;
    }
    return now;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (now.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