Submission #645766

#	Time	Username	Problem	Language	Result	Execution time	Memory
645766		rodov	Brperm (RMI20_brperm)	C++14	50 / 100	130 ms	19056 KiB

brperm

#include <iostream>
#include <vector>
#include <cstring>
#include "brperm.h"

using namespace std;

vector <int> v[20];
vector <pair<int, int>> checks[20];

inline void pregen(void)
{
    int i, j;
    v[0].push_back(0);

    for(i = 1; i <= 19; ++ i)
    {
        for(j = 0; j < 1 << i - 1; ++ j)
            v[i].push_back(v[i - 1][j] * 2);

        for(j = 0; j < 1 << i - 1; ++ j)
            v[i].push_back(v[i][j] + 1);
    }

    for(i = 0; i <= 19; ++ i)
        for(j = 0; j < 1 << (i - 1); ++ j)
            if(j != v[i][j])
                checks[i].push_back(make_pair(j, v[i][j]));
}

const int NMAX = 5e5;
char arr[NMAX + 5];
int dp[NMAX + 5];
int f[30];
int dim, ok = 1;

void init(int n, const char s[])
{
    dim = n;
    strcpy(arr, s);
    int i;
    for(i = 0; i < n; ++ i)
        f[s[i] - 'a'] = 1;

    for(i = 2; i < 26; ++ i)
        if(f[i])
            ok = 0;

    if(ok == 1)
        for(i = 0; i < n; ++ i)
            dp[i] = dp[i - 1] + (s[i] == 'a');
    pregen();
}

int query(int i, int k)
{
    if((i + (1 << k) - 1) >= dim)
        return 0;

    if(ok)
    {
        int val = dp[i + (1 << k) - 1];
        if(i) val -= dp[i - 1];
        if(!val || val == 1 << k)
            return 1;
        if(val != 1 << (k - 1))
            return 0;
    }

    int j;
    for(j = 0; j < checks[k].size(); ++ j)
        if(arr[i + checks[k][j].first] != arr[i + checks[k][j].second])
            return 0;

    return 1;
}

Compilation message (stderr)

brperm.cpp: In function 'void pregen()':
brperm.cpp:18:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   18 |         for(j = 0; j < 1 << i - 1; ++ j)
      |                             ~~^~~
brperm.cpp:21:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |         for(j = 0; j < 1 << i - 1; ++ j)
      |                             ~~^~~
brperm.cpp: In function 'int query(int, int)':
brperm.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(j = 0; j < checks[k].size(); ++ j)
      |                ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 0 / 17
• Subtask 4: 0 / 33