Submission #442212

#	Time	Username	Problem	Language	Result	Execution time	Memory
442212		mario05092929	Martian DNA (IOI16_dna)	C++11	100 / 100	14 ms	460 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
string ask;
int tmp;

string analyse(int n, int t) {
    int row = 0,i;
    for(i = 0;i < n;i++) {
        int val = rand()%2;
        ask += (char)(val+'0');
        tmp = make_test(ask);
        if(!tmp) {
            row++;
            ask.pop_back();
            ask += (char)(val^1+'0');
            if(row > 13) {i++; break;}
        }
        else row = 0;
    }
    int l = 0, r = i-1;
    string ask2;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        ask2.clear();
        for(int i = 0;i <= mid;i++) ask2 += ask[i];
        tmp = make_test(ask2);
        if(tmp) l = mid;
        else r = mid-1;
    }
    ask2.clear();
    for(i = 0;i <= l;i++) ask2 += ask[i];
    ask = ask2;
    int sz = ask.length();
    for(i = 0;i < n-sz;i++) {
        ask = "0"+ask;
        tmp = make_test(ask);
        if(!tmp) {
            ask[0] = '1';
        }
    }
    return ask;
}

Compilation message (stderr)

dna.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
dna.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
dna.cpp:9: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      | 
dna.cpp: In function 'std::string analyse(int, int)':
dna.cpp:37:32: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   37 |             ask += (char)(val^1+'0');
      |                               ~^~~~
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