oj.uz

Submission #366267

# Submission time Handle Problem Language Result Execution time Memory
366267 2021-02-13T17:35:17 Z rocks03 Secret (JOI14_secret) C++14
30 / 100
 600 ms 9216 KB 
    //#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 200 ms 5612 KB Output is partially correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 7
2 Partially correct 192 ms 5612 KB Output is partially correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 7
3 Partially correct 190 ms 5612 KB Output is partially correct - number of calls to Secret by Init = 3604, maximum number of calls to Secret by Query = 7
4 Partially correct 600 ms 9196 KB Output is partially correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 8
5 Partially correct 592 ms 9216 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
6 Partially correct 525 ms 6264 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 2
7 Partially correct 552 ms 6636 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
8 Partially correct 548 ms 6704 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 6
9 Partially correct 565 ms 7928 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 8
10 Partially correct 554 ms 6784 KB Output is partially correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 7