제출 #366269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366269		rocks03	비밀 (JOI14_secret)	C++14	100 / 100	575 ms	6780 KiB

secret

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
// #include "secret.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

map<pii, int> memo;
int Secret(int x, int y);
int queries = 0;
const int MAXQ = 8000;
int ask(int x, int y){
    if(memo.count({x, y}))
        return memo[{x, y}];
    queries++;
    //if(queries > MAXQ) return 0;
    memo[{x, y}] = Secret(x, y);
  	memo[{y, x}] = memo[{x, y}];
	return memo[{x, y}];
}

const int MAXK = 10;
const int MAXN = 1e3;
int *a, st[MAXK][MAXN], mask[MAXN];

void solve(int l, int r, int lev){
    if(l == r) return;
    int m = (l + r) / 2;
    solve(l, m, lev + 1); solve(m + 1, r, lev + 1);
    st[lev][m] = a[m];
    Re(i, m - 1, l){
        st[lev][i] = ask(a[i], st[lev][i + 1]);
    }
    st[lev][m + 1] = a[m + 1];
    rep(i, m + 2, r + 1){
        st[lev][i] = ask(st[lev][i - 1], a[i]);
    }
    rep(i, m + 1, r + 1){
        mask[i] ^= (1 << lev);
    }
}

void Init(int N, int A[]){
    a = A;
    solve(0, N - 1, 0);
}

int Query(int L, int R){
    if(L == R) return a[L];
    int bits = __builtin_ctz(mask[L] ^ mask[R]);
    return ask(st[bits][L], st[bits][R]);
}

• Subtask 1: 100 / 100