oj.uz

Submission #54741

# Submission time Handle Problem Language Result Execution time Memory
54741 2018-07-04T23:35:43 Z luciocf Martian DNA (IOI16_dna) C++14
11 / 100
 93 ms 1368 KB 
#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

int n;

string get(int k, int qual)
{
    string s = "";
    for (int i = 1; i <= k; i++)
    {
        if (qual) s += "1";
        else s += "0";
    }
    return s;
}

int busca(string s, int x, int qual, int ordem)
{
    int ini = 0, fim = x;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        if (!ordem)
        {
            if (make_test(s+get(mid, qual))) ini = mid+1;
            else fim = mid-1;
        }
        else
        {
            if (make_test(get(mid, qual)+s)) ini = mid+1;
            else fim = mid-1;
        }
    }
    return fim;
}

string analyse(int k, int t)
{
    n = k;

    int size = 0;
    string s = "";

    int flag = 0;
    if (!busca(s, n, 0, 0)) flag = 1;

    while (true)
    {
        int x = busca(s, n-size, flag, 0);
        if (!x) break;

        size += x;
        s += get(x, flag);
        flag = !flag;
    }
    if (size == n) return s;

    flag = 0;
    if (!busca(s, n-size, 0, 1)) flag = 1;
    while (true)
    {
        int x = busca(s, n-size, flag, 1);
        if (!x) return s;

        size += x;
        string ant = get(x, flag);
        s = ant+s;
        flag = !flag;
    }
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 3 ms 680 KB Output is correct
9 Correct 2 ms 680 KB Output is correct
10 Correct 3 ms 680 KB Output is correct
11 Correct 4 ms 680 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 688 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 2 ms 744 KB Output is correct
17 Correct 2 ms 744 KB Output is correct
18 Correct 3 ms 744 KB Output is correct
19 Correct 2 ms 744 KB Output is correct
20 Correct 2 ms 792 KB Output is correct
21 Correct 3 ms 792 KB Output is correct
22 Correct 2 ms 812 KB Output is correct
23 Correct 2 ms 812 KB Output is correct
24 Correct 2 ms 812 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 3 ms 812 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 3 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 2 ms 848 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 3 ms 848 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Incorrect 2 ms 848 KB Too many tests
18 Incorrect 2 ms 848 KB Too many tests
19 Incorrect 2 ms 848 KB Too many tests
20 Incorrect 4 ms 848 KB Too many tests
21 Incorrect 3 ms 848 KB Too many tests
22 Incorrect 3 ms 848 KB Too many tests
23 Incorrect 4 ms 848 KB Too many tests
24 Correct 2 ms 848 KB Output is correct
25 Correct 3 ms 848 KB Output is correct
26 Correct 2 ms 848 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Incorrect 3 ms 848 KB Too many tests
29 Incorrect 3 ms 848 KB Too many tests
30 Incorrect 3 ms 848 KB Too many tests
31 Incorrect 3 ms 848 KB Too many tests
32 Incorrect 3 ms 848 KB Too many tests
33 Correct 2 ms 848 KB Output is correct
34 Correct 2 ms 852 KB Output is correct

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 2 ms 864 KB Output is correct
6 Correct 2 ms 868 KB Output is correct
7 Correct 2 ms 872 KB Output is correct
8 Correct 2 ms 996 KB Output is correct
9 Correct 2 ms 996 KB Output is correct
10 Correct 2 ms 996 KB Output is correct
11 Correct 2 ms 996 KB Output is correct
12 Correct 2 ms 996 KB Output is correct
13 Correct 2 ms 996 KB Output is correct
14 Correct 2 ms 996 KB Output is correct
15 Correct 2 ms 996 KB Output is correct
16 Correct 2 ms 996 KB Output is correct
17 Correct 3 ms 996 KB Output is correct
18 Correct 3 ms 996 KB Output is correct
19 Correct 4 ms 996 KB Output is correct
20 Correct 4 ms 996 KB Output is correct
21 Correct 4 ms 996 KB Output is correct
22 Incorrect 82 ms 1056 KB Too many tests
23 Incorrect 74 ms 1092 KB Too many tests
24 Incorrect 63 ms 1100 KB Too many tests
25 Incorrect 84 ms 1104 KB Too many tests
26 Incorrect 80 ms 1104 KB Too many tests
27 Incorrect 69 ms 1108 KB Too many tests
28 Incorrect 77 ms 1112 KB Too many tests
29 Correct 2 ms 1116 KB Output is correct
30 Correct 2 ms 1120 KB Output is correct
31 Correct 2 ms 1124 KB Output is correct
32 Correct 3 ms 1128 KB Output is correct
33 Incorrect 85 ms 1132 KB Too many tests
34 Incorrect 89 ms 1368 KB Too many tests
35 Incorrect 83 ms 1368 KB Too many tests
36 Incorrect 93 ms 1368 KB Too many tests
37 Incorrect 76 ms 1368 KB Too many tests
38 Correct 3 ms 1368 KB Output is correct
39 Correct 3 ms 1368 KB Output is correct