Submission #982153

#	Time	Username	Problem	Language	Result	Execution time	Memory
982153		justinlgl20	Martian DNA (IOI16_dna)	C++14	36 / 100	9 ms	600 KiB

dna

#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 = 9; 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);*/
            for (int j = 0; j < zeros; j++) {
                ans += '0';
                if (!make_test(ans)) {
                    ans.pop_back();
                    break;
                }
            }
            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 (stderr)

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:95:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     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 / 11
• Subtask 2: 25 / 25
• Subtask 3: 0 / 64