Submission #251422

#	Time	Username	Problem	Language	Result	Execution time	Memory
251422		StevenH	Martian DNA (IOI16_dna)	C++14	100 / 100	15 ms	384 KiB

dna

#include "dna.h"

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <random>
using namespace std;

string analyse(int n, int t)
{

    string str = "";
    bool flag = 0;
    int cnt = 0;
    int k = 12;
    while (str.size() < n || cnt != 0)
    {
        if (flag == 0)
        {
            string a, b;
            if (rand() % 2)
                a = "0", b = "1";
            else
                a = "1", b = "0";
            if (make_test(str + a))
                str += a, cnt = 0;
            else
            {
                if (cnt == k)
                {
                    if (!make_test(str + b))
                    {
                        // int l = 1, r = k;
                        // while (l < r)
                        // {
                        //     int mid = (l + r + 1) / 2;
                        //     string res = str.substr(0, str.size() - k + mid);
                        //     if (make_test(res))
                        //         l = mid;
                        //     else
                        //         r = mid - 1;
                        // }
                        // str = str.substr(0, str.size() - k + l);
                        int tag;
                        for (int i = 1; i <= cnt; i++)
                        {
                            if (make_test(str.substr(0, str.size() - cnt + i)))
                                tag = i;
                            else
                                break;
                        }
                        str = str.substr(0, str.size() - cnt + tag);
                        flag = 1;
                        cnt = 0;
                        continue;
                    }
                    else
                    {
                        str += b;
                        cnt = 0;
                        continue;
                    }
                }
                else
                    str += b, cnt++;
            }
        }
        if (flag == 1)
        {
            if (make_test("0" + str))
                str = "0" + str;
            else
                str = "1" + str;
        }
        if (str.size() == n)
        {
            // int l = 1, r = cnt;
            // while (l < r)
            // {
            //     int mid = (l + r + 1) / 2;
            //     string res = str.substr(0, str.size() - cnt + mid);
            //     if (make_test(res))
            //     {
            //         l = mid;
            //     }
            //     else
            //         r = mid - 1;
            // }
            // str = str.substr(0, str.size() - cnt + l);

            int tag;
            for (int i = 1; i <= cnt; i++)
            {
                if (make_test(str.substr(0, str.size() - cnt + i)))
                    tag = i;
                else
                    break;
            }
            str = str.substr(0, str.size() - cnt + tag);
            flag = 1;
            cnt = 0;
        }
    }
    return str;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (str.size() < n || cnt != 0)
            ~~~~~~~~~~~^~~
dna.cpp:75:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (str.size() == n)
             ~~~~~~~~~~~^~~~
dna.cpp:91:17: warning: 'tag' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int tag;
                 ^~~
dna.cpp:44:29: warning: 'tag' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int tag;
                             ^~~
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