Submission #471459

#	Time	Username	Problem	Language	Result	Execution time	Memory
471459		flappybird	Martian DNA (IOI16_dna)	C++14	100 / 100	16 ms	420 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;

std::string analyse(int N, int t) {
	string s;
	ll l, r;
	l = 0, r = N + 1;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		string q;
		for (ll i = 1; i <= mid; i++) q.push_back('1');
		if (make_test(q)) l = mid;
		else r = mid;
	}
	ll i;
	if (l == 0) {
		for (i = 1; i <= N; i++) s.push_back('0');
		return s;
	}
	for (i = 1; i <= l; i++) s.push_back('1');
	ll streak = 0;
	while (1) {
		s.insert(s.begin(), '0');
		if (make_test(s)) streak = 0;
		else {
			streak++;
			if (streak > l) {
				for (i = 0; i <= l; i++) s.erase(s.begin());
				ll low, high;
				low = 0, high = l + 1;
				while (high - low > 1) {
					ll mid = (low + high) / 2;
					for (i = 1; i <= mid; i++) s.insert(s.begin(), '1');
					if (make_test(s)) low = mid;
					else high = mid;
					for (i = 1; i <= mid; i++) s.erase(s.begin());
				}
				for (i = 1; i <= low; i++) s.insert(s.begin(), '1');
				break;
			}
			else {
				s.erase(s.begin());
				s.insert(s.begin(), '1');
			}
		}
	}
	while (s.size() < N) {
		s.push_back('0');
		if (!make_test(s)) s[s.size() - 1] = '1';
	}
	return s;
}

Compilation message (stderr)

dna.cpp: In function 'std::string analyse(int, int)':
dna.cpp:50:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  while (s.size() < N) {
      |         ~~~~~~~~~^~~
grader.cpp: In function 'bool make_test(std::string)':
grader.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 1; i <= ss.size(); i++) {
      |                  ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if (pr[i] == p.size()) {

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 64 / 64