Submission #1221781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221781		anonymous321	Brperm (RMI20_brperm)	C++20	0 / 100	1443 ms	327680 KiB

brperm

#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;
int MAXL;

vector<vector<bool>> sol;

struct node {
    map<int, int> child {};
    set<int> id {};
};

void init(int n, const char s[]) {
    MAXL = __lg(n) + 1;
    sol = vector<vector<bool>> (n, vector<bool>(MAXL, false));
    vector<node> trie {{}};
    for (int i = 0; i < n; i++) {
        int cur = 0;
        for (int j = i; j < min(i + MAXL, n); j++) {
            int c = s[j] - 'a';
            if (trie[cur].child.count(c) == 0) {
                trie[cur].child[c] = trie.size();
                trie.push_back({});
            }
            cur = trie[cur].child[c];
            trie[cur].id.insert(i);
        }
    }
    
    for (int i = n-1; i >= 0; i--) {
        int cur = 0;
        for (int j = i; j >= max(i - MAXL + 1, 0); j--) {
            int c = s[j] - 'a';
            if (trie[cur].child.count(c) == 0) {
                break;
            }
            cur = trie[cur].child[c];
            if (trie[cur].id.count(j) == 1) {
                sol[j][i - j] = true;
            }
        }
    }
    return;
}

int query(int i, int k) {
    if (k == 0) return true;
    if (i + (1 << k) > sol.size()) return false;
    if (i+1 >= sol.size()) return false;
    return sol[i+1][k-1];
}

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