답안 #434768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434768	2021-06-21T18:57:10 Z	Odavey	Martian DNA (IOI16_dna)	C++14	100 / 100	15 ms	480 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct

Subtask #2

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	1 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct

Subtask #3

64.0 / 64.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	10 ms	332 KB	Output is correct
23	Correct	11 ms	460 KB	Output is correct
24	Correct	10 ms	380 KB	Output is correct
25	Correct	14 ms	332 KB	Output is correct
26	Correct	13 ms	356 KB	Output is correct
27	Correct	8 ms	332 KB	Output is correct
28	Correct	7 ms	372 KB	Output is correct
29	Correct	15 ms	332 KB	Output is correct
30	Correct	6 ms	372 KB	Output is correct
31	Correct	7 ms	332 KB	Output is correct
32	Correct	15 ms	204 KB	Output is correct
33	Correct	9 ms	480 KB	Output is correct
34	Correct	9 ms	356 KB	Output is correct
35	Correct	8 ms	368 KB	Output is correct
36	Correct	8 ms	332 KB	Output is correct
37	Correct	8 ms	332 KB	Output is correct
38	Correct	11 ms	332 KB	Output is correct
39	Correct	10 ms	360 KB	Output is correct