Submission #398515

#	Time	Username	Problem	Language	Result	Execution time	Memory
398515		model_code	Brperm (RMI20_brperm)	C++17	50 / 100	3060 ms	12576 KiB

brperm

/**
* user:  aelenei-a68
* fname: Alex-Ioan
* lname: Aelenei
* task:  Brperm
* score: 83.0
* date:  2020-12-03 09:14:55.678394
*/
#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 dim;

void init(int n, const char s[])
{
    dim = n;
    strcpy(arr, s);
    pregen();
}

int query(int i, int k)
{
    if((i + (1 << k) - 1) > dim)
        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:26:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 |         for(j = 0; j < 1 << i - 1; ++ j)
      |                             ~~^~~
brperm.cpp:29:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |         for(j = 0; j < 1 << i - 1; ++ j)
      |                             ~~^~~
brperm.cpp: In function 'int query(int, int)':
brperm.cpp:56: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]
   56 |     for(j = 0; j < checks[k].size(); ++ j)
      |                ~~^~~~~~~~~~~~~~~~~~

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