Submission #1190637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190637		pcheloveks	Brperm (RMI20_brperm)	C++20	0 / 100	161 ms	327680 KiB

brperm

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Andrusha Holod did not qualify to IOI 2025 )))
//Hope Andrusha Holod will win IOI 2026

#include "brperm.h"

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair < int, ull > piu;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 100007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 1e9 + 123;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[5] = { -1, -1, 0, 1, 0 };
const ll dy[5] = { -1, 0, -1, 0, 1 };

FILE* stream;

ll getval(char val) {
    return val - 'a' + 1;
}

class polyHash {
public:
    const ll base = 31;

    vector < int > powll;
    vector < ull > powull;

    vector < int > prefll;
    vector < ull > prefull;

    void count(const string& s) {
        ll n = s.length();

        powll.resize(n + 7);
        powull.resize(n + 7);
        prefll.resize(n + 7);
        prefull.resize(n + 7);

        powll[0] = 1;
        powull[0] = 1;

        for (int i = 1; i <= n; i++) {
            powll[i] = (powll[i - 1] * base) % mod;
            powull[i] = (powull[i - 1] * base);

            if (powll[i] < 0) powll[i] += mod;
        }

        prefll[0] = 0;
        prefull[0] = 0;

        for (int i = 1; i <= n; i++) {
            prefll[i] = ((prefll[i - 1] * base) + getval(s[i - 1])) % mod;
            prefull[i] = (prefull[i - 1] * base) + getval(s[i - 1]);

            if (prefll[i] < 0) prefll[i] += mod;
        }
    }

    piu gethash(ll L, ll R) {
        ll len = R - L + 1;
        int hashll = prefll[R] - (powll[len] * prefll[L - 1]) % mod;
        ull hashull = prefull[R] - (powull[len] * prefull[L - 1]);


        if (hashll < 0) hashll += mod;

        return { hashll, hashull };
    }

    piu mergeHash(piu h1, piu h2, ll len) {
        piu res;
        res.first = (h1.first * powll[len] + h2.first) % mod;
        res.second = h1.second * powull[len] + h2.second;

        if (res.first < 0) res.first += mod;

        return res;
    }
};

polyHash h;
vector < vector < vector < piu > > > H;

ll N;
vector < ll > powers(30);

void init(int n, const char s[]) {

    N = n;
    h.count(s);

    ll r = 1, p = 0;
    while (2 * r <= n) {
        r *= 2;
        p++;
    }

    H.resize(DIM);
    for (int i = 0; i < DIM; i++) {
        H[i].resize(18);
        for (int j = 0; j < 18; j++) {
            H[i][j].resize(18);
        }
    }

    powers[0] = 1;
    for (int i = 1; i <= p; i++) powers[i] = (2 * powers[i - 1]) % mod;

    for (int i = n - 1; i >= 0; i--) {
        for (int k = 0; k <= p; k++) {
            for (int j = 0; j <= p; j++) {
                //cout << i << " " << k << " " << j << endl;
                if (n - i < powers[j] * (powers[k] - 1) + 1) continue;


                if (k == 0) H[i][j][k] = h.gethash(i + 1, i + 1);
                else {
                    H[i][j][k] = h.mergeHash(H[i][j + 1][k - 1], H[i + powers[j]][j + 1][k - 1], powers[k - 1]);
                }
            }
        }
    }
}

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

    if (h.gethash(i + 1, i + powers[k]) == H[i][0][k]) return 1;
    else return 0;
}

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