oj.uz

Submission #398515

# Submission time Handle Problem Language Result Execution time Memory
398515 2021-05-04T12:47:25 Z model_code Brperm (RMI20_brperm) C++17
50 / 100
 3060 ms 12576 KB 
/**
* 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

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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10620 KB Output is correct
2 Correct 14 ms 10620 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10620 KB Output is correct
2 Correct 14 ms 10620 KB Output is correct
3 Correct 38 ms 10908 KB Output is correct
4 Correct 38 ms 10988 KB Output is correct
5 Correct 46 ms 10992 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10620 KB Output is correct
2 Correct 14 ms 10620 KB Output is correct
3 Correct 38 ms 10908 KB Output is correct
4 Correct 38 ms 10988 KB Output is correct
5 Correct 46 ms 10992 KB Output is correct
6 Incorrect 3060 ms 12576 KB Output isn't correct
7 Halted 0 ms 0 KB -