Submission #54937

#	Time	Username	Problem	Language	Result	Execution time	Memory
54937		luciocf	Martian DNA (IOI16_dna)	C++14	100 / 100	19 ms	648 KiB

dna

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

using namespace std;

int n;
string s;

string get(int k)
{
    string ans = "";
    for (int i = 1; i <= k; i++)
        ans += "0";
    return ans;
}

string get2(int k)
{
    string ans = "";
    for (int i = 0; i < k; i++)
        ans += s[i];
    return ans;
}

int busca(void)
{
    int ini = 1, fim = n;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        if (make_test(get(mid))) ini = mid+1;
        else fim = mid-1;
    }
    return fim;
}

int busca2(void)
{
    int ini = 1, fim = n;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        if (make_test(get2(mid))) ini = mid+1;
        else fim = mid-1;
    }
    return fim;
}

string analyse(int k, int t)
{
    n = k;

    int size = 0;
    s = "";

    if (!make_test("0"))
    {
        for (int i = 1; i <= n; i++) s += "1";
        return s;
    }

    int qtd = busca();
    size = qtd;
    s = get(qtd);

    while (size < n)
    {
        if (!make_test(s+"1"))
        {
            int x = 0;
            for (int i = s.size()-1; i >= 0; i--)
            {
                if (s[i] != '0') break;
                x++;
            }
            if (x > qtd) break;
            s += "0", size++;
        }
        else s += "1", size++;
    }
    int pos = busca2();

    string ans = get2(pos);
    size = ans.size();

    if (size == n) return ans;

    while (size < n)
    {
        if (make_test("1"+ans)) ans = "1"+ans;
        else ans = "0"+ans;
        size++;
    }
    return ans;
}

Compilation message (stderr)

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