Submission #434768

#	Time	Username	Problem	Language	Result	Execution time	Memory
434768		Odavey	Martian DNA (IOI16_dna)	C++14	100 / 100	15 ms	480 KiB

dna

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

bool make_test(string p);

string n_zeroes(int n){
    string res = "";
    for(int i=0;i<n;++i){
        res += '0';
    }
    return res;
}

int longest_zeroes(int n){
    int lo = 0;
    int hi = n;
    while(lo < hi){
        int mid = (lo+hi+1)/2;
        if(make_test(n_zeroes(mid))){
            lo = mid;
        }else{
            hi = mid-1;
        }
    }
    return lo;
}

string analyse(int n, int t){
    int M = longest_zeroes(n);
    int doubt = 0;
    string res = n_zeroes(M);
    while(doubt <= M){
        if(make_test(res+'1')){
            doubt = 0;
            res += '1';
        }else{
            ++doubt;
            res += '0';
        }
    }
    int lo = 0;
    int hi = doubt;
    while(lo < hi){
        int mid = (lo+hi)/2;
        if(make_test(res.substr(0, (int)res.size()-mid))){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
    res = res.substr(0, (int)res.size()-lo);
    while((int)res.size() < n){
        if(make_test('1' + res)){
            res = '1' + res;
        }else{
            res = '0' + res;
        }
    }
    return res;
}

Compilation message (stderr)

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: 64 / 64