Submission #92919

#	Time	Username	Problem	Language	Result	Execution time	Memory
92919		dim131	Martian DNA (IOI16_dna)	C++14	100 / 100	14 ms	380 KiB

dna

#include "dna.h"

#include <cstdlib>
#include <iostream>

std::string generatek01(int k) {
  std::string seq;
  for (int i = 0; i < k; ++i) {
    seq += "01";
  }
  return seq;
}

int findLargest01(int n, int t) {
  int st = 0, en = n /2;
  while (st < en) {
    int mid = (st + en + 1) / 2;
	if (make_test(generatek01(mid))) {
	  st = mid;
	} else {
	  en = mid - 1;
	}
  }
  return st;
}

char otherChar(char c) {
  return c == '0' ? '1' : '0';
}

std::string analyse(int n, int t) {
    int len = findLargest01(n, t);
	// std::cout << "Largest was " << len << std::endl;
	int unverified_len = 0;
	char currentChar = '0';
	std::string seq = generatek01(len);
	len *= 2;
	// Find right.
	while(true) {
	  if (make_test(seq + currentChar)) {
	    unverified_len = 0;
		seq += currentChar;
	  } else {
		currentChar = otherChar(currentChar);
		seq += currentChar;
		++unverified_len;
	  }
	  if (unverified_len > len || seq.size() > n) break;
	}
	int normal_len = seq.size() - unverified_len;
	// Binary search verified length. 
	int st = 0, en = unverified_len;
	while (st < en) {
	  int mid = (st + en + 1) / 2;
	  if (make_test(seq.substr(0, normal_len + mid))) st = mid;
      else en = mid - 1;
	}
    seq = seq.substr(0, normal_len + st);
	// std::cout << "Normal string : " <<  seq << std::endl;
	normal_len = seq.size();
    for (int i = normal_len; i < n; ++i) {
      if (make_test('0' + seq)) {
        seq = '0' + seq;
      } else seq = '1' + seq;
    }	  
	// std::cout << "Found " << seq << std::endl;
    return seq;
}                       

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:48:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (unverified_len > len || seq.size() > n) break;
                                ~~~~~~~~~~~^~~
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