oj.uz

Submission #645766

# Submission time Handle Problem Language Result Execution time Memory
645766 2022-09-28T00:13:33 Z rodov Brperm (RMI20_brperm) C++14
50 / 100
 130 ms 19056 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10628 KB Output is correct
2 Correct 12 ms 10632 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10628 KB Output is correct
2 Correct 12 ms 10632 KB Output is correct
3 Correct 32 ms 11020 KB Output is correct
4 Correct 32 ms 11024 KB Output is correct
5 Correct 32 ms 10996 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 19056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10628 KB Output is correct
2 Correct 12 ms 10632 KB Output is correct
3 Correct 32 ms 11020 KB Output is correct
4 Correct 32 ms 11024 KB Output is correct
5 Correct 32 ms 10996 KB Output is correct
6 Incorrect 130 ms 19056 KB Output isn't correct
7 Halted 0 ms 0 KB -