제출 #1135857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135857		Thanhs	Secret (JOI14_secret)	C++20	0 / 100	331 ms	4508 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e3 + 5;

map<pair<int, int>, int> mp;
int n, a[NM], A[NM], sum = 0;
pair<int, int> b[NM][NM];

void dnc(int l, int r)
{
    if (l >= r)
        return;
    int m = l + r >> 1;
    for (int i = l; i < m; i++)
        mp[{l, m}] = Query(a[i], a[m]);
    for (int i = m + 2; i <= r; i++)
        mp[{m + 1, i}] = Query(a[m + 1], a[i]);
    for (int i = l; i <= m; i++)
        for (int j = m + 1; j <= r; j++)
            b[i][j] = {mp[{i, m}], mp[{m + 1, j}]};
    dnc(l, m); 
    dnc(m + 1, r);
}

void Init(int N, int A[])
{
    n = N;
    for (int i = 1; i <= n; i++)
    {
        a[i] = A[i - 1];
        mp[{i, i}] = a[i];
    }
    dnc(1, n);
}

int Query(int l, int r)
{
    l++; r++;
    if (l == r)
        return a[l];
    return Query(b[l][r].fi, b[l][r].se);
}

• Subtask 1: 0 / 100