Submission #116088

#	Time	Username	Problem	Language	Result	Execution time	Memory
116088		tjd229	Martian DNA (IOI16_dna)	C++14	100 / 100	15 ms	404 KiB

dna

#include "dna.h"

#include <cstdlib>
#define reg register
std::string make_str(int len, char c) {
	std::string s = "";
	for (reg int i = 0; i < len; ++i) s += c;
	return s;
}
std::string analyse(int n, int t) {
	int cnt = 0;
	int l = 1, r = n;
	while (l <= r) {
		int m = (l + r) >> 1;
		if(make_test(make_str(m,'0'))) cnt=m,l=m+1;
		else r=m-1;
	}
	if (!cnt) return make_str(n,'1');
	std::string s = make_str(cnt, '0');
	int stk = cnt;
	while (s.size()<n && stk<=cnt) {//len<n && stk
		if (make_test(s + '1')) s += '1',stk=0;
		else s += '0',++stk;
	}
	if (s.size() == n && make_test(s)) return s;
	int bnd = s.size() - stk;
	std::string sub = "";
	for (reg int i = 0; i < bnd; ++i) sub += s[i];
	l = 0, r = stk - 1; cnt = 0;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (make_test(sub + make_str(m, '0'))) cnt=m,l = m + 1;
		else r = m - 1;
	}
	s = sub + make_str(cnt,'0');
	while (s.size() < n) {
		s = '1' + s;
		if (!make_test(s)) s[0] = '0';
	}
	return s;
}                       

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:21:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (s.size()<n && stk<=cnt) {//len<n && stk
         ~~~~~~~~^~
dna.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (s.size() == n && make_test(s)) return s;
      ~~~~~~~~~^~~~
dna.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (s.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