Submission #21811

# Submission time Handle Problem Language Result Execution time Memory
21811 2017-04-25T21:53:59 Z sampriti Martian DNA (IOI16_dna) C++14
100 / 100
13 ms 2024 KB
#include "dna.h"

#include <cstdlib>
#include <cassert>
#include <string>
#include <algorithm>
#include <ctime>

using namespace std;

string analyse(int N, int t) {
  int L = 0, R = N;
  while(L < R) {
    int mid = (L + R + 1)/2;
    string S = "";
    for(int i = 0; i < mid; i++) S += "1";

    if(make_test(S)) L = mid;
    else R = mid - 1;
  }
  int longest_1 = L;

  string ans = "";

  if(longest_1 == 0) {
    for(int i = 0; i < N; i++) ans += "0";
    return ans;
  }

  for(int i = 0; i < longest_1; i++) {
    ans += "1";
  }

  int false_cnt = 0;
  while(false_cnt <= longest_1) {
    if(make_test(ans + "0")) {
      ans += "0";
      false_cnt = 0;
    }
    else {
      ans += "1";
      false_cnt++;
    }
  }

  L = 1, R = ans.size();
  while(L < R) {
    int mid = (L + R + 1)/2;
    if(make_test(ans.substr(0, mid))) {
      L = mid;
    }
    else {
      R = mid - 1;
    }
  }
  ans = ans.substr(0, L);

  while(ans.size() < N) {
    if(make_test("0" + ans)) ans = "0" + ans;
    else ans = "1" + ans;
  }

  return ans;
}

Compilation message

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:58: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()) {
             ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 0 ms 2024 KB Output is correct
14 Correct 0 ms 2024 KB Output is correct
15 Correct 0 ms 2024 KB Output is correct
16 Correct 0 ms 2024 KB Output is correct
17 Correct 0 ms 2024 KB Output is correct
18 Correct 0 ms 2024 KB Output is correct
19 Correct 0 ms 2024 KB Output is correct
20 Correct 0 ms 2024 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct
22 Correct 0 ms 2024 KB Output is correct
23 Correct 0 ms 2024 KB Output is correct
24 Correct 0 ms 2024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 0 ms 2024 KB Output is correct
14 Correct 0 ms 2024 KB Output is correct
15 Correct 0 ms 2024 KB Output is correct
16 Correct 0 ms 2024 KB Output is correct
17 Correct 0 ms 2024 KB Output is correct
18 Correct 0 ms 2024 KB Output is correct
19 Correct 0 ms 2024 KB Output is correct
20 Correct 0 ms 2024 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct
22 Correct 0 ms 2024 KB Output is correct
23 Correct 0 ms 2024 KB Output is correct
24 Correct 0 ms 2024 KB Output is correct
25 Correct 0 ms 2024 KB Output is correct
26 Correct 0 ms 2024 KB Output is correct
27 Correct 0 ms 2024 KB Output is correct
28 Correct 0 ms 2024 KB Output is correct
29 Correct 0 ms 2024 KB Output is correct
30 Correct 0 ms 2024 KB Output is correct
31 Correct 0 ms 2024 KB Output is correct
32 Correct 0 ms 2024 KB Output is correct
33 Correct 0 ms 2024 KB Output is correct
34 Correct 0 ms 2024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 0 ms 2024 KB Output is correct
14 Correct 0 ms 2024 KB Output is correct
15 Correct 0 ms 2024 KB Output is correct
16 Correct 0 ms 2024 KB Output is correct
17 Correct 0 ms 2024 KB Output is correct
18 Correct 0 ms 2024 KB Output is correct
19 Correct 0 ms 2024 KB Output is correct
20 Correct 0 ms 2024 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct
22 Correct 9 ms 2024 KB Output is correct
23 Correct 9 ms 2024 KB Output is correct
24 Correct 9 ms 2024 KB Output is correct
25 Correct 9 ms 2024 KB Output is correct
26 Correct 9 ms 2024 KB Output is correct
27 Correct 6 ms 2024 KB Output is correct
28 Correct 6 ms 2024 KB Output is correct
29 Correct 0 ms 2024 KB Output is correct
30 Correct 13 ms 2024 KB Output is correct
31 Correct 13 ms 2024 KB Output is correct
32 Correct 3 ms 2024 KB Output is correct
33 Correct 6 ms 2024 KB Output is correct
34 Correct 6 ms 2024 KB Output is correct
35 Correct 6 ms 2024 KB Output is correct
36 Correct 6 ms 2024 KB Output is correct
37 Correct 9 ms 2024 KB Output is correct
38 Correct 9 ms 2024 KB Output is correct
39 Correct 9 ms 2024 KB Output is correct