Submission #159265

#	Time	Username	Problem	Language	Result	Execution time	Memory
159265		Leonardo_Paes	Martian DNA (IOI16_dna)	C++14	100 / 100	16 ms	504 KiB

dna

#include "dna.h"
#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

bool check1(int x){
    string s;
    s.resize(x);
    for(int i=0; i<x; i++) s[i] = '1';
    return make_test(s);
}

bool check2(int x, string aux){
    string s;
    s.resize(x);
    for(int i=0; i<x; i++) s[i] = aux[i];
    return make_test(s);
}

string analyse(int n, int t){
    if(!make_test("1")){
        string a;
        a.resize(n);
        for(int i=0; i<n; i++) a[i] = '0';
        return a;
    }

    int ini = 0, fim = n, meio, longest1 = 0;

    while(ini <= fim){
        meio = (ini + fim) >> 1;

        if(check1(meio)){
            longest1 = meio;
            ini = meio + 1;
        }
        else{
            fim = meio-1;
        }
    }

    string s;
    for(int i=0; i<longest1; i++) s += '1';

    int consec1 = longest1;

    while(consec1<=longest1){
        string aux = s;
        aux += '0';
        if(make_test(aux)){
            s += '0';
            consec1 = 0;
        }
        else{
            s += '1';
            consec1++;
        }
    }

    ini = (int)s.size() - consec1, fim = (int)s.size();

    int idend;

    while(ini <= fim){
        meio = (ini + fim ) >> 1;

        if(check2(meio, s)){
            idend = meio;
            ini = meio + 1;
        }
        else{
            fim = meio - 1;
        }
    }

    deque<char> ans;
    for(int i=0; i<idend; i++) ans.push_back(s[i]);

    while(ans.size() < n){
        ans.push_front('1');
        string aux;
        aux.resize((int)ans.size());
        for(int i=0; i<ans.size(); i++) aux[i] = ans[i];
        if(!make_test(aux)){
            ans.pop_front();
            ans.push_front('0');
        }
    }

    string true_ans;
    true_ans.resize(n);
    for(int i=0; i<ans.size(); i++) true_ans[i] = ans[i];

    return true_ans;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ans.size() < n){
           ~~~~~~~~~~~^~~
dna.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<ans.size(); i++) aux[i] = ans[i];
                      ~^~~~~~~~~~~
dna.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++) true_ans[i] = ans[i];
                  ~^~~~~~~~~~~
dna.cpp:63:9: warning: 'idend' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int idend;
         ^~~~~
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