Submission #60274

#	Time	Username	Problem	Language	Result	Execution time	Memory
60274		kingpig9	Martian DNA (IOI16_dna)	C++11	100 / 100	22 ms	760 KiB

dna

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

string analyse (int n, int t) {
	//find zeroes max
	int lo = 0, hi = n + 1;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (make_test(string(mid, '0'))) {
			lo = mid;
		} else {
			hi = mid;
		}
	}

	if (lo == n) {
		return string(n, '0');
	}
	if (lo == 0) {
		return string(n, '1');
	}

	int mxzero = lo;
	string ans(mxzero, '0');
	for (int i = 0; i < n - mxzero; i++) {
		if (make_test(ans + '1')) {
			ans += '1';
		} else {
			int end0 = 0;
			for (int j = ans.size() - 1; j >= 0; j--) {
				if (ans[j] != '0') {
					break;
				}
				end0++;
			}

			if (end0 > mxzero) {
				break;
			}
			ans += '0';
		}
	}

	lo = mxzero;
	hi = ans.size() + 1;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (make_test(ans.substr(0, mid))) {
			lo = mid;
		} else {
			hi = mid;
		}
	}

	ans = ans.substr(0, lo);
	while (ans.size() < n) {
		if (make_test('1' + ans)) {
			ans = '1' + ans;
		} else {
			ans = '0' + ans;
		}
	}
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:67: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