Submission #54741

#	Time	Username	Problem	Language	Result	Execution time	Memory
54741		luciocf	Martian DNA (IOI16_dna)	C++14	11 / 100	93 ms	1368 KiB

dna

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

using namespace std;

int n;

string get(int k, int qual)
{
    string s = "";
    for (int i = 1; i <= k; i++)
    {
        if (qual) s += "1";
        else s += "0";
    }
    return s;
}

int busca(string s, int x, int qual, int ordem)
{
    int ini = 0, fim = x;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        if (!ordem)
        {
            if (make_test(s+get(mid, qual))) ini = mid+1;
            else fim = mid-1;
        }
        else
        {
            if (make_test(get(mid, qual)+s)) ini = mid+1;
            else fim = mid-1;
        }
    }
    return fim;
}

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

    int size = 0;
    string s = "";

    int flag = 0;
    if (!busca(s, n, 0, 0)) flag = 1;

    while (true)
    {
        int x = busca(s, n-size, flag, 0);
        if (!x) break;

        size += x;
        s += get(x, flag);
        flag = !flag;
    }
    if (size == n) return s;

    flag = 0;
    if (!busca(s, n-size, 0, 1)) flag = 1;
    while (true)
    {
        int x = busca(s, n-size, flag, 1);
        if (!x) return s;

        size += x;
        string ant = get(x, flag);
        s = ant+s;
        flag = !flag;
    }
}

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: 0 / 25
• Subtask 3: 0 / 64