Submission #21811

#	Time	Username	Problem	Language	Result	Execution time	Memory
21811		sampriti	Martian DNA (IOI16_dna)	C++14	100 / 100	13 ms	2024 KiB

dna

#include "dna.h"

#include <cstdlib>
#include <cassert>
#include <string>
#include <algorithm>
#include <ctime>

using namespace std;

string analyse(int N, int t) {
  int L = 0, R = N;
  while(L < R) {
    int mid = (L + R + 1)/2;
    string S = "";
    for(int i = 0; i < mid; i++) S += "1";

    if(make_test(S)) L = mid;
    else R = mid - 1;
  }
  int longest_1 = L;

  string ans = "";

  if(longest_1 == 0) {
    for(int i = 0; i < N; i++) ans += "0";
    return ans;
  }

  for(int i = 0; i < longest_1; i++) {
    ans += "1";
  }

  int false_cnt = 0;
  while(false_cnt <= longest_1) {
    if(make_test(ans + "0")) {
      ans += "0";
      false_cnt = 0;
    }
    else {
      ans += "1";
      false_cnt++;
    }
  }

  L = 1, R = ans.size();
  while(L < R) {
    int mid = (L + R + 1)/2;
    if(make_test(ans.substr(0, mid))) {
      L = mid;
    }
    else {
      R = mid - 1;
    }
  }
  ans = ans.substr(0, L);

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

  return ans;
}

Compilation message (stderr)

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