Submission #366267

#	Time	Username	Problem	Language	Result	Execution time	Memory
366267		rocks03	Secret (JOI14_secret)	C++14	30 / 100	600 ms	9216 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];
     
    void Init(int N, int A[]){
        a = A;
        rep(i, 0, N){
            st[0][i] = a[i];
        }
        rep(k, 0, MAXK - 1){
            rep(i, 0, N + 1 - (1 << (k + 1))){
                st[k + 1][i] = ask(st[k][i], st[k][i + (1 << k)]);
            }
        }
    }
     
    int Query(int L, int R){
        int ans = INT_MAX;
        Re(k, MAXK - 1, 0){
            if((R - L + 1) >> k & 1){
                if(ans == INT_MAX) ans = st[k][L];
                else ans = ask(ans, st[k][L]);
                L += (1 << k);
            }
        }
        return ans;
    }

• Subtask 1: 30 / 100