제출 #746406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746406		doowey	Brperm (RMI20_brperm)	C++14	13 / 100	1480 ms	262144 KiB

brperm

#include <bits/stdc++.h>
#include "brperm.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MOD = (int)1e9 + 9;
const int N = (int)5e5 + 10;
const int K = 19;
const int B = 77;
vector<char> S;
map<pii, int> dp[N];
int pwr[N];

int make(int i, int step, int lim){
    if(dp[i][mp(step, lim)] != 0) return dp[i][mp(step, lim)];
    if(step == lim){
        //cout << i << " ";
        return S[i] - 'a' + 1;
    }
    int lef, rig;
    lef = make(i, step + 1, lim);
    rig = make(i + (1 << step), step + 1, lim);
    //cout << "merge: " << lef << " + " << rig << "\n";
    lef += (rig * 1ll * pwr[(1<<(lim-step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return dp[i][mp(step,lim)]=lef;
}

int H[N][K];

int make2(int i, int step){
    if(H[i][step] != 0) return H[i][step];
    if(step == 0){
        return S[i] - 'a' + 1;
    }
    int lef = make2(i, step - 1);
    int rig = make2(i + (1 << (step - 1)), step - 1);
    lef += (rig * 1ll * pwr[(1 << (step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return H[i][step] = lef;
}

void init(int n, const char s[]) {
    pwr[0] = 1;
    for(int i = 1; i <= n; i ++ ) pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    for(int i = 0 ; i < n; i ++ ){
        S.push_back(s[i]);
    }
}

int query(int i, int k) {
    if(i + (1 << k) - 1 >= S.size()) return 0;
    int ca = make(i, 0, k);
    int cb = make2(i, k);
    //cout << ca << " " << cb << " |\n";
    return (ca==cb);
}

컴파일 시 표준 에러 (stderr) 메시지

brperm.cpp: In function 'int query(int, int)':
brperm.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(i + (1 << k) - 1 >= S.size()) return 0;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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