oj.uz

Submission #92917

# Submission time Handle Problem Language Result Execution time Memory
92917 2019-01-05T15:32:29 Z dim131 Martian DNA (IOI16_dna) C++14
0 / 100
 13 ms 504 KB 
#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);
	// 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 360 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 252 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 376 KB Wrong DNA
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 352 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Incorrect 2 ms 256 KB Wrong DNA
14 Incorrect 2 ms 128 KB Wrong DNA
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 292 KB Output is correct
18 Incorrect 2 ms 376 KB Wrong DNA
19 Incorrect 2 ms 376 KB Wrong DNA
20 Correct 9 ms 256 KB Output is correct
21 Incorrect 2 ms 376 KB Wrong DNA
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 396 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Incorrect 2 ms 376 KB Wrong DNA
29 Correct 2 ms 376 KB Output is correct
30 Incorrect 2 ms 256 KB Wrong DNA
31 Incorrect 2 ms 256 KB Wrong DNA
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Incorrect 2 ms 256 KB Wrong DNA
13 Incorrect 2 ms 256 KB Wrong DNA
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Incorrect 2 ms 376 KB Wrong DNA
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 2 ms 376 KB Wrong DNA
21 Incorrect 2 ms 376 KB Wrong DNA
22 Incorrect 9 ms 376 KB Wrong DNA
23 Incorrect 11 ms 376 KB Wrong DNA
24 Incorrect 9 ms 376 KB Wrong DNA
25 Correct 13 ms 376 KB Output is correct
26 Incorrect 12 ms 376 KB Wrong DNA
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 7 ms 376 KB Output is correct
30 Correct 10 ms 376 KB Output is correct
31 Correct 7 ms 376 KB Output is correct
32 Correct 7 ms 376 KB Output is correct
33 Incorrect 8 ms 376 KB Wrong DNA
34 Incorrect 7 ms 376 KB Wrong DNA
35 Correct 8 ms 376 KB Output is correct
36 Incorrect 7 ms 376 KB Wrong DNA
37 Incorrect 8 ms 376 KB Wrong DNA
38 Correct 8 ms 412 KB Output is correct
39 Correct 9 ms 376 KB Output is correct