oj.uz

Submission #767123

# Submission time Handle Problem Language Result Execution time Memory
767123 2023-06-26T12:00:50 Z tolbi Dungeons Game (IOI21_dungeons) C++17
62 / 100
 1044 ms 2097152 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulHamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename T> vector<int32_t> normalize(vector<T> &rt){vector<int32_t> arr(rt.size());for (int i = 0; i < rt.size(); i++){arr[i]=rt[i];}return arr;}
#define endl '\n'
#define int long long
#define vint(x) vector<int> x
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define tol(bi) (1LL<<((int)(bi)))
#define lsb(x) (x&-x)
const int MOD = 1e9+7;
const int64_t INF = 1e15;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "dungeons.h"
vector<int32_t> s,p,w,l;
int n;
vector<vector<int>> st2;
vector<vector<int>> val2;
vector<vector<int>> mava2;
vector<vector<vector<int>>> st;
vector<vector<vector<int>>> val;
set<int> ele;
map<int,int> mp;
vector<int> revmp;
const int LOG = 60;
bool bb;
int mvv;
void init(int32_t _n, vector<int32_t> _s, vector<int32_t> _p, vector<int32_t> _w, vector<int32_t> _l) {
    n=_n,s=_s,p=_p,w=_w,l=_l;
    mvv = *max_element(s.begin(), s.end());
    mvv = max(mvv,(int)*max_element(p.begin(), p.end()));
    st2.resize(n+1,vector<int>(LOG,-1));
    val2.resize(n+1,vector<int>(LOG,-1));
    mava2.resize(n+1,vector<int>(LOG,-1));
    for (int node = 0; node < n; node++){
        st2[node][0]=w[node];
        mava2[node][0]=s[node];
        val2[node][0]=s[node];
    }
    for (int bit = 1; bit < LOG; bit++){
        for (int node = 0; node < n; node++){
            if (st2[node][bit-1]==-1) continue;
            st2[node][bit]=st2[st2[node][bit-1]][bit-1];
            if (st2[node][bit]==-1) continue;
            val2[node][bit]=val2[node][bit-1]+val2[st2[node][bit-1]][bit-1];
            mava2[node][bit]=max(mava2[node][bit-1],mava2[st2[node][bit-1]][bit-1]);
            if (val2[node][bit]>INF){
                val2[node][bit]=st2[node][bit]=mava2[node][bit]=-1;
            }
        }
    }
    bb=true;
    for (int i = 0; i < n; ++i)
    {
        if (s[i]!=p[i]){
            bb=false;
            break;
        }
    }
    if (bb) {
        return;
    }
    if (mvv<=10000) return;
    ele.insert(0);
    for (int i = 0; i < s.size(); i++){
        ele.insert(s[i]);
    }
    int ind = 0;
    for (auto it : ele){
        mp[it]=ind++;
        revmp.push_back(it);
    }
    st2.clear();
    val2.clear();
    mava2.clear();
    st.resize(ind,vector<vector<int>>(n+1,vector<int>(LOG,-1)));
    val.resize(ind,vector<vector<int>>(n+1,vector<int>(LOG,-1)));
    for (int el = 0; el < ind; el++){
        int va = revmp[el];
        int sin = INF;
        if (el<ind-1) sin = revmp[el+1]-revmp[el];
        for (int i = 0; i < n; i++){
            if (va>=s[i]){
                st[el][i][0]=w[i];
                val[el][i][0]=s[i];
            }
            else {
                st[el][i][0]=l[i];
                val[el][i][0]=p[i];
            }
            if (val[el][i][0]>=sin) {
                st[el][i][0]=val[el][i][0]=-1;
            }
        }
        for (int bit = 1; bit < LOG; bit++){
            for (int i = 0; i < n; ++i)
            {
                if (st[el][i][bit-1]==-1) continue;
                st[el][i][bit]=st[el][st[el][i][bit-1]][bit-1];
                if (st[el][i][bit]==-1) continue;
                val[el][i][bit]=val[el][i][bit-1]+val[el][st[el][i][bit-1]][bit-1];
                if (val[el][i][bit]>=sin){
                    st[el][i][bit]=val[el][i][bit]=-1;
                }
            }
        }
    }
}
int simul2(int x, int z){
    for (int bit = LOG-1; bit >= 0; bit--){
        if (st2[x][bit]==-1) continue;
        if (z<mava2[x][bit]) continue;
        z+=val2[x][bit];
        x=st2[x][bit];
    }
    if (x==n) return z;
    if (z>=s[x]){
        z+=s[x];
        x=w[x];
    }
    else {
        z+=p[x];
        x=l[x];
    }
    return simul2(x,z);
}
int bk(int x){
    auto it = ele.lower_bound(x+1);
    it--;
    return *it;
}
int sonr(int x){
    auto it = ele.lower_bound(x+1);
    if (it==ele.end()) return INF;
    return *it;
}
int64_t simul(int32_t x, int64_t z){
    int cur = mp[bk(z)];
    int cc = sonr(z);
    for (int bit = LOG-1; bit >= 0; bit--){
        if (st[cur][x][bit]==-1) continue;
        if (val[cur][x][bit]+z>=cc) continue;
        z+=val[cur][x][bit];
        x=st[cur][x][bit];
    }
    if (x==n) return z;
    if (z>=s[x]){
        z+=s[x];
        x=w[x];
    }
    else {
        z+=p[x];
        x=l[x];
    }
    return simul(x,z);
}
int64_t simulate(int32_t x, int32_t z) {
    if (mvv<=10000){
        int nss = z;
        while (nss<=mvv && x!=n){
            if (nss>=s[x]){
                nss+=s[x];
                x=w[x];
            }
            else {
                nss+=p[x];
                x=l[x];
            }
        }
        for (int bit = LOG-1; bit >= 0; bit--){
            if (st2[x][bit]==-1) continue;
            nss+=val2[x][bit];
            x=st2[x][bit];
        }
        return nss;
    }
    int ans;
    if (!bb){
        ans=simul(x,z);
    }
    else ans = simul2(x,z);
    return ans;
}

Compilation message

dungeons.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
dungeons.cpp: In function 'void init(int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:81:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < s.size(); i++){
      |                     ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 71 ms 78984 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 72 ms 78940 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 856 ms 633960 KB Output is correct
3 Correct 851 ms 634444 KB Output is correct
4 Correct 817 ms 634796 KB Output is correct
5 Correct 747 ms 635048 KB Output is correct
6 Correct 922 ms 634556 KB Output is correct
7 Correct 956 ms 633900 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 202 ms 134088 KB Output is correct
3 Correct 216 ms 134092 KB Output is correct
4 Correct 199 ms 134040 KB Output is correct
5 Correct 114 ms 79704 KB Output is correct
6 Correct 210 ms 134312 KB Output is correct
7 Correct 212 ms 134076 KB Output is correct
8 Correct 117 ms 79704 KB Output is correct
9 Correct 102 ms 79652 KB Output is correct
10 Correct 118 ms 79688 KB Output is correct
11 Correct 223 ms 134092 KB Output is correct
12 Correct 333 ms 134120 KB Output is correct
13 Correct 279 ms 134092 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 202 ms 134088 KB Output is correct
3 Correct 216 ms 134092 KB Output is correct
4 Correct 199 ms 134040 KB Output is correct
5 Correct 114 ms 79704 KB Output is correct
6 Correct 210 ms 134312 KB Output is correct
7 Correct 212 ms 134076 KB Output is correct
8 Correct 117 ms 79704 KB Output is correct
9 Correct 102 ms 79652 KB Output is correct
10 Correct 118 ms 79688 KB Output is correct
11 Correct 223 ms 134092 KB Output is correct
12 Correct 333 ms 134120 KB Output is correct
13 Correct 279 ms 134092 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 278 ms 235872 KB Output is correct
16 Correct 335 ms 286796 KB Output is correct
17 Correct 392 ms 337600 KB Output is correct
18 Correct 437 ms 337768 KB Output is correct
19 Correct 403 ms 337612 KB Output is correct
20 Correct 341 ms 235932 KB Output is correct
21 Correct 404 ms 286708 KB Output is correct
22 Correct 274 ms 184924 KB Output is correct
23 Correct 404 ms 286716 KB Output is correct
24 Correct 436 ms 235924 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 202 ms 134088 KB Output is correct
3 Correct 216 ms 134092 KB Output is correct
4 Correct 199 ms 134040 KB Output is correct
5 Correct 114 ms 79704 KB Output is correct
6 Correct 210 ms 134312 KB Output is correct
7 Correct 212 ms 134076 KB Output is correct
8 Correct 117 ms 79704 KB Output is correct
9 Correct 102 ms 79652 KB Output is correct
10 Correct 118 ms 79688 KB Output is correct
11 Correct 223 ms 134092 KB Output is correct
12 Correct 333 ms 134120 KB Output is correct
13 Correct 279 ms 134092 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 278 ms 235872 KB Output is correct
16 Correct 335 ms 286796 KB Output is correct
17 Correct 392 ms 337600 KB Output is correct
18 Correct 437 ms 337768 KB Output is correct
19 Correct 403 ms 337612 KB Output is correct
20 Correct 341 ms 235932 KB Output is correct
21 Correct 404 ms 286708 KB Output is correct
22 Correct 274 ms 184924 KB Output is correct
23 Correct 404 ms 286716 KB Output is correct
24 Correct 436 ms 235924 KB Output is correct
25 Runtime error 1044 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 856 ms 633960 KB Output is correct
3 Correct 851 ms 634444 KB Output is correct
4 Correct 817 ms 634796 KB Output is correct
5 Correct 747 ms 635048 KB Output is correct
6 Correct 922 ms 634556 KB Output is correct
7 Correct 956 ms 633900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 202 ms 134088 KB Output is correct
10 Correct 216 ms 134092 KB Output is correct
11 Correct 199 ms 134040 KB Output is correct
12 Correct 114 ms 79704 KB Output is correct
13 Correct 210 ms 134312 KB Output is correct
14 Correct 212 ms 134076 KB Output is correct
15 Correct 117 ms 79704 KB Output is correct
16 Correct 102 ms 79652 KB Output is correct
17 Correct 118 ms 79688 KB Output is correct
18 Correct 223 ms 134092 KB Output is correct
19 Correct 333 ms 134120 KB Output is correct
20 Correct 279 ms 134092 KB Output is correct
21 Correct 4 ms 5972 KB Output is correct
22 Correct 278 ms 235872 KB Output is correct
23 Correct 335 ms 286796 KB Output is correct
24 Correct 392 ms 337600 KB Output is correct
25 Correct 437 ms 337768 KB Output is correct
26 Correct 403 ms 337612 KB Output is correct
27 Correct 341 ms 235932 KB Output is correct
28 Correct 404 ms 286708 KB Output is correct
29 Correct 274 ms 184924 KB Output is correct
30 Correct 404 ms 286716 KB Output is correct
31 Correct 436 ms 235924 KB Output is correct
32 Runtime error 1044 ms 2097152 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -