Submission #1175886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175886		redstonegamer22	Secret (JOI14_secret)	C++20	100 / 100	349 ms	5484 KiB

secret

#include "secret.h"

#include <vector>
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <cassert>

std::map<std::pair<int, int>, int> secret_map;
int mySecret(int X, int Y) {
    if(X == -2) return Y;
    if(Y == -2) return X;

    if(X == -1 || Y == -1) {
        return -1;
    }

    if(secret_map.find({X, Y}) != secret_map.end()) {
        return secret_map[{X, Y}];
    }

    return secret_map[{X, Y}] = Secret(X, Y);
}

struct DisjointSparseTable {
    int lg2;
    std::vector<std::vector<int>> table;

    DisjointSparseTable() {}

    DisjointSparseTable(std::vector<int> a) {
        {
            const int n = a.size();
            lg2 = 0;
            while ((1 << lg2) < n) {
                ++lg2;
            }
            assert((1 << lg2) >= n);
        }

        const int n = (1 << lg2);
        a.resize(n, -1);

        table.resize(lg2 + 1, a);

        for(int level = 1; level <= lg2; level++) {
            const int segment_size = (1 << level);

            for(int segment_start = 0; segment_start < n; segment_start += segment_size) {
                const int segment_end = segment_start + segment_size - 1;
                const int mid = segment_start + segment_size / 2 - 1;
                // segmentul meu e impartit la jumate ca [segment_start, mid] si [mid + 1, segment_end]
                
                for(int i = mid - 1; i >= segment_start; i--) {
                    table[level][i] = mySecret(table[level][i], table[level][i + 1]);
                }
                for(int i = mid + 2; i <= segment_end; i++) {
                    table[level][i] = mySecret(table[level][i - 1], table[level][i]);
                }
            }
        }
    }

    int query(int st, int dr) {
        if(st == dr) {
            return table[0][st]; // evident doar un element
        }

        int diff = st ^ dr;
    
        // daca st si dr au un mijloc intre ele pe nivelul k
        // inseamna ca st <= segment_start + 2^(k - 1) - 1
        // si dr >= segment_start + 2^(k - 1)
        // segment_start la randul lui este divizibil cu 2^k
        // segment_start = segment_size * i
        // segment_start + 2^(k - 1) - 1 = segment_size * i + (segment_size / 2) - 1
        //                                   \--------> are k de 0 la final in binar
        // ?????????[k de 0] + 1[k - 1 de 0] - 1 = ???????????0[k - 1 de 1]
        // st <= ?????????0[k - 1 de 1]
        // dr >= ?????????[k de 1]
        //         \-------> foarte important, aceste ??????? sunt acelasi prefix si pentru st si pentru dr
        // st = [prefix]0[????]
        // dr = [prefix]1[????]
        // st ^ dr = [prefix]1[????] ^ [prefix]0[????] = [0 de |prefix| ori]1[?????]
        // noi stim ca 1[?????] trebuie sa fie la fel de lung ca sufixul de k de 0
        // deci daca stiu pozitia primului 1 in st ^ dr, stiu si k

        int nivel = 32 - __builtin_clz(diff); // parte intreaga a log2(diff)

        // std::cerr << "query: " << st << " " << dr << std::endl;
        // std::cerr << "nivel: " << nivel << std::endl;

        return mySecret(table[nivel][st], table[nivel][dr]);
    }
} dst;

void Init(int N, int A[]) {
    std::vector<int> v(N);
    for(int i = 0; i < N; i++) {
        v[i] = A[i];
    }
    dst = DisjointSparseTable(v);
}

int Query(int L, int R) {
    return dst.query(L, R);
}

• Subtask 1: 100 / 100