Submission #1091503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091503		rjvkr2021	Martian DNA (IOI16_dna)	C++17	36 / 100	1098 ms	1072 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
bool is_substring(string &txt, string &pat){
    string s = pat + "#" + txt;
    int n = s.size();
    vector<int> pi(n);
    pi[0] = 0;
    int l = 0, i = 1;
    while(i < n){
        if(s[i] == s[l]){
            l++;
            pi[i] = l;
            i++;
        }
        else{
            if(l == 0){
                pi[i] = 0;
                i++;
            }
            else{
                l = pi[l - 1];
            }
        }
    }
    for(int i = pat.size() + 1; i < n; i++){
        if(pi[i] == pat.size()){
            return true;
        }
    }
    return false;
}
string analyse(int n, int t) {
    vector<string> yes, no;
    string query;
    auto valid_query = [&](){
        if(query.size() > n){
            return false;
        }
        for(string &t: yes){
            if(!is_substring(query, t)){
                return false;
            }
        }
        for(string &t: no){
            if(is_substring(query, t)){
                return false;
            }
        }
        return true;
    };
    bool response;
    bool suffix_found = false;
    while(true){
        if(suffix_found){
            query.insert(query.begin(), '0'); // try zero
            if(valid_query()){
                response = make_test(query);
                if(response){
                    yes.pb(query);
                    continue;
                }
                else{
                    no.pb(query);
                }
            }
            query[0] = '1'; // try one
            if(valid_query()){
                response = make_test(query);
                if(response){
                    yes.pb(query);
                    continue;
                }
                else{
                    no.pb(query);
                }
            }
            query.erase(query.begin());
            return query;
        }
        else{
            query.pb('0'); // try zero
            if(valid_query()){
                response = make_test(query);
                if(response){
                    yes.pb(query);
                    continue;
                }
                else{
                    no.pb(query);
                }
            }
            query.back() = '1'; // try one
            if(valid_query()){
                response = make_test(query);
                if(response){
                    yes.pb(query);
                    continue;
                }
                else{
                    no.pb(query);
                }
            }
            query.pop_back();
            suffix_found = true;
        }
    }
}

Compilation message (stderr)

dna.cpp: In function 'bool is_substring(std::string&, std::string&)':
dna.cpp:28:18: 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(pi[i] == pat.size()){
dna.cpp: In lambda function:
dna.cpp:38:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if(query.size() > n){
      |            ~~~~~~~~~~~~~^~~
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