Submission #437199

#	Time	Username	Problem	Language	Result	Execution time	Memory
437199		ryno	Martian DNA (IOI16_dna)	C++14	100 / 100	16 ms	388 KiB

dna

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include "dna.h"
using namespace std;

int N, T, len;

string makeStr(int size, char c = '0') {
	string s = "";
	for (int rep = 0; rep < size; ++rep) s.push_back(c);
	return s;
}

bool endswith(string s, string suffix) {
	// does s end with suffix;
	if (s.size() < suffix.size()) return false;
	while (!suffix.empty()) {
		if (s.back() != suffix.back()) return false;
		s.pop_back();
		suffix.pop_back();
	}
	return true;
}

int maxLen() {
	int l = 0, r = N + 1;
	while (l + 1 < r) {
		int m = (l + r) / 2;
		if (make_test(makeStr(m))) l = m;
		else r = m;
	}
	return l;
}

string extendRight(string curr) {
	do {
		if (make_test(curr + '1')) {
			curr.push_back('1');
		}
		else {
			// assume its a 0, even though it might be the end of the string
			curr.push_back('0');
		}
	} while (!endswith(curr, makeStr(len + 1)));
	return curr;
}

string cullRight(string curr) {
	int l = curr.size() - len - 1, r = curr.size() + 1;
	while (l + 1 < r) {
		int m = (l + r) / 2;
		if (make_test(curr.substr(0, m))) l = m;
		else r = m;
	}
	return curr.substr(0, l);
}

string extendLeft(string curr) {
	while (curr.size() < N) {
		if (make_test('1' + curr)) {
			curr = '1' + curr;
		}
		else {
			// assume its a 0, even though it might be the end of the string
			curr = '0' + curr;
		}
	}
	return curr;
}

string analyse(int n, int t) {
	N = n;
	T = t;
	len = maxLen();

	if (len == 0) return makeStr(N, '1');
	
	string curr = makeStr(len);
	//cout << curr << "\n";
	curr = extendRight(curr);
	//cout << curr << "\n";
	curr = cullRight(curr);
	//cout << curr << "\n";
	curr = extendLeft(curr);
	//cout << curr << "\n";
	return curr;
}

/*int main() {
	if (ans != analyse(ans.size(), -1)) throw 20;
	cout << numTests;
}*/

Compilation message (stderr)

dna.cpp: In function 'std::string extendLeft(std::string)':
dna.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |  while (curr.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