oj.uz

Submission #982151

# Submission time Handle Problem Language Result Execution time Memory
982151 2024-05-14T01:16:12 Z justinlgl20 Martian DNA (IOI16_dna) C++14
11 / 100
 10 ms 756 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
        os << "{"; int g = o.size(); for (auto i : o) os << i << ((--g)==0?"":", "); os << "}";
    return os;
}

void _print() {
        cout << "]\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
        cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m" <<__func__ << ":" <<__LINE__ << " [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

int nxt() {
    int g; cin >> g; return g;
}


string analyse(int n, int t) {
    string ans;
    int l = 1, i;
    for (l = 0, i = 10; i >= 0; i-=1) {
        if (l + 1<<i <= n) {
            // try l + 1<<i;
            string x;
            for (int j = 0; j < l + 1<<i; j++) {
                x += '0';
            }
            if (make_test(x)) {
                l += 1<<i;
            }
        }
    }
    dbg("ZEROS", l);
    // the string contains l*"0"
    for (int i = 0; i < l; i++) ans += '0';
    int start = -1;
    int zeros = 0;
    i = 0;
    while (true) {
        ans += '1';
        if (make_test(ans)) zeros = 0;
        else {
            ans.pop_back();
            ans += '0';
            dbg("ADD");
            zeros++;
        }

        if (zeros > l) {
            dbg("EXCEEDED");
            for (int j = 0; j < zeros; j++) ans.pop_back();
            // bsearch on amount of 0s we need to add;
            int idk, z;
            for (idk = 0, z = 10; z >= 0; z--) {
                if (idk + 1<<z > zeros) continue;
                for (int _ = 0; _ < idk + 1<<z; _++) {
                    ans += "0";
                }
                if (make_test(ans)) idk += 1<<z;
                else {
                    for (int p = 0; p < idk + 1<<z; p++) ans.pop_back();
                }
            }
            dbg(idk);
            break;
        }
        i++;
    }
    while (ans.size() < n) {
        string s = "0"+ans;
        if (make_test(s)) {ans = s;dbg("ADD 0");}
        else {ans = "1"+ans; dbg("ADD 1");}
    }
    return ans;
}

Compilation message

dna.cpp: In function 'std::string analyse(int, int)':
dna.cpp:41:15: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |         if (l + 1<<i <= n) {
      |             ~~^~~
dna.cpp:44:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   44 |             for (int j = 0; j < l + 1<<i; j++) {
      |                                 ~~^~~
dna.cpp:74:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   74 |                 if (idk + 1<<z > zeros) continue;
      |                     ~~~~^~~
dna.cpp:75:41: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   75 |                 for (int _ = 0; _ < idk + 1<<z; _++) {
      |                                     ~~~~^~~
dna.cpp:80:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   80 |                     for (int p = 0; p < idk + 1<<z; p++) ans.pop_back();
      |                                         ~~~~^~~
dna.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |     while (ans.size() < n) {
      |            ~~~~~~~~~~~^~~
dna.cpp:55:9: warning: unused variable 'start' [-Wunused-variable]
   55 |     int start = -1;
      |         ^~~~~
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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 356 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Correct 0 ms 352 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 356 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 420 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 7 ms 508 KB Output is correct
23 Correct 8 ms 356 KB Output is correct
24 Incorrect 7 ms 348 KB Wrong DNA
25 Incorrect 8 ms 752 KB Wrong DNA
26 Correct 10 ms 348 KB Output is correct
27 Correct 5 ms 348 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 6 ms 348 KB Output is correct
30 Correct 5 ms 348 KB Output is correct
31 Correct 5 ms 440 KB Output is correct
32 Correct 6 ms 476 KB Output is correct
33 Correct 7 ms 348 KB Output is correct
34 Correct 7 ms 528 KB Output is correct
35 Correct 6 ms 344 KB Output is correct
36 Correct 7 ms 348 KB Output is correct
37 Correct 6 ms 348 KB Output is correct
38 Correct 7 ms 512 KB Output is correct
39 Correct 7 ms 348 KB Output is correct