oj.uz

Submission #622846

# Submission time Handle Problem Language Result Execution time Memory
622846 2022-08-04T16:35:28 Z Bench0310 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5930 ms 486856 KB 
#include <bits/stdc++.h>
#include "dungeons.h"
#pragma GCC target ("popcnt")

using namespace std;
typedef long long ll;

const int C=5; //cutoff between naive jumping and building base-4 jumps
const int N=400001;
int n;
int s[N];
int p[N];
int w[N];
int l[N];
int jump[N][11-C][12];
ll boost[N][11-C][12];
int mn[N][11-C][12];
int won[N];
int to[N];
int pw[N];
ll end_boost[N];
const int inf=(1<<30);
const int lim=10000000;

int msb(ll a)
{
    int b=63-__builtin_clzll(a);
    return (b/2);
}

void build(int lvl)
{
    for(int i=0;i<n;i++)
    {
        won[i]=(msb(s[i])<=lvl+C);
        to[i]=(won[i]==1?w[i]:l[i]);
        pw[i]=(won[i]==1?s[i]:p[i]);
    }
    won[n]=1; to[n]=n; pw[n]=0;
    //j=0
    for(int i=0;i<=n;i++)
    {
        jump[i][lvl][0]=to[i];
        boost[i][lvl][0]=pw[i];
        mn[i][lvl][0]=(won[i]==0?s[i]:inf);
    }
    //j>0
    for(int j=1;j<12;j++)
    {
        for(int i=0;i<=n;i++)
        {
            int a=i;
            ll b=0;
            int m=inf;
            for(int k=0;k<4;k++)
            {
                m=min(m,int(max(ll(0),mn[a][lvl][j-1]-b)));
                b+=boost[a][lvl][j-1];
                a=jump[a][lvl][j-1];
            }
            jump[i][lvl][j]=a;
            boost[i][lvl][j]=b;
            mn[i][lvl][j]=m;
        }
    }
}

void build_end()
{
    end_boost[n]=0;
    for(int i=n-1;i>=0;i--) end_boost[i]=s[i]+end_boost[w[i]];
}

void init(int tn,vector<int> ts,vector<int> tp,vector<int> tw,vector<int> tl)
{
    n=tn;
    for(int i=0;i<n;i++){s[i]=ts[i]; p[i]=tp[i]; w[i]=tw[i]; l[i]=tl[i];}
    for(int i=0;i<=10-C;i++) build(i);
    build_end();
}

ll simulate(int a,int z)
{
    ll b=z;
    auto mv=[&]()
    {
        if(b>=s[a])
        {
            b+=s[a];
            a=w[a];
        }
        else
        {
            b+=p[a];
            a=l[a];
        }
    };
    while(b<=(1<<(2*(C+1)))-1)
    {
        mv();
        if(a==n) return b;
    }
    while(a!=n)
    {
        int lvl=min(msb(b)-1,11)-C;
        if(lvl==11-C) break;
        while(a!=n&&min(msb(b)-1,11)-C==lvl)
        {
            for(int j=11;j>=0;j--)
            {
                for(int k=0;k<3;k++)
                {
                    if(jump[a][lvl][j]!=n&&b<mn[a][lvl][j])
                    {
                        b+=boost[a][lvl][j];
                        a=jump[a][lvl][j];
                    }
                }
            }
            mv();
        }
    }
    b+=end_boost[a];
    return b;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 260 ms 60564 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 254 ms 60564 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1620 KB Output is correct
2 Correct 2467 ms 479168 KB Output is correct
3 Correct 2605 ms 479168 KB Output is correct
4 Correct 2439 ms 479172 KB Output is correct
5 Correct 2419 ms 479164 KB Output is correct
6 Correct 2950 ms 479164 KB Output is correct
7 Correct 3740 ms 479680 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1596 KB Output is correct
2 Correct 385 ms 61892 KB Output is correct
3 Correct 330 ms 62104 KB Output is correct
4 Correct 364 ms 61856 KB Output is correct
5 Correct 316 ms 61872 KB Output is correct
6 Correct 355 ms 61988 KB Output is correct
7 Correct 645 ms 61964 KB Output is correct
8 Correct 306 ms 61752 KB Output is correct
9 Correct 281 ms 61896 KB Output is correct
10 Correct 445 ms 61724 KB Output is correct
11 Correct 2312 ms 62000 KB Output is correct
12 Correct 2423 ms 61964 KB Output is correct
13 Correct 973 ms 61972 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1596 KB Output is correct
2 Correct 385 ms 61892 KB Output is correct
3 Correct 330 ms 62104 KB Output is correct
4 Correct 364 ms 61856 KB Output is correct
5 Correct 316 ms 61872 KB Output is correct
6 Correct 355 ms 61988 KB Output is correct
7 Correct 645 ms 61964 KB Output is correct
8 Correct 306 ms 61752 KB Output is correct
9 Correct 281 ms 61896 KB Output is correct
10 Correct 445 ms 61724 KB Output is correct
11 Correct 2312 ms 62000 KB Output is correct
12 Correct 2423 ms 61964 KB Output is correct
13 Correct 973 ms 61972 KB Output is correct
14 Correct 4 ms 1516 KB Output is correct
15 Correct 327 ms 61788 KB Output is correct
16 Correct 378 ms 61872 KB Output is correct
17 Correct 313 ms 61696 KB Output is correct
18 Correct 321 ms 61772 KB Output is correct
19 Correct 406 ms 61964 KB Output is correct
20 Correct 372 ms 61744 KB Output is correct
21 Correct 280 ms 61868 KB Output is correct
22 Correct 937 ms 61848 KB Output is correct
23 Correct 2457 ms 61728 KB Output is correct
24 Correct 1141 ms 61992 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1596 KB Output is correct
2 Correct 385 ms 61892 KB Output is correct
3 Correct 330 ms 62104 KB Output is correct
4 Correct 364 ms 61856 KB Output is correct
5 Correct 316 ms 61872 KB Output is correct
6 Correct 355 ms 61988 KB Output is correct
7 Correct 645 ms 61964 KB Output is correct
8 Correct 306 ms 61752 KB Output is correct
9 Correct 281 ms 61896 KB Output is correct
10 Correct 445 ms 61724 KB Output is correct
11 Correct 2312 ms 62000 KB Output is correct
12 Correct 2423 ms 61964 KB Output is correct
13 Correct 973 ms 61972 KB Output is correct
14 Correct 4 ms 1516 KB Output is correct
15 Correct 327 ms 61788 KB Output is correct
16 Correct 378 ms 61872 KB Output is correct
17 Correct 313 ms 61696 KB Output is correct
18 Correct 321 ms 61772 KB Output is correct
19 Correct 406 ms 61964 KB Output is correct
20 Correct 372 ms 61744 KB Output is correct
21 Correct 280 ms 61868 KB Output is correct
22 Correct 937 ms 61848 KB Output is correct
23 Correct 2457 ms 61728 KB Output is correct
24 Correct 1141 ms 61992 KB Output is correct
25 Correct 348 ms 61164 KB Output is correct
26 Correct 422 ms 61860 KB Output is correct
27 Correct 315 ms 61900 KB Output is correct
28 Correct 343 ms 61488 KB Output is correct
29 Correct 405 ms 61740 KB Output is correct
30 Correct 420 ms 61676 KB Output is correct
31 Correct 425 ms 61644 KB Output is correct
32 Correct 941 ms 61736 KB Output is correct
33 Correct 555 ms 61712 KB Output is correct
34 Correct 858 ms 61392 KB Output is correct
35 Correct 563 ms 61568 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1620 KB Output is correct
2 Correct 2467 ms 479168 KB Output is correct
3 Correct 2605 ms 479168 KB Output is correct
4 Correct 2439 ms 479172 KB Output is correct
5 Correct 2419 ms 479164 KB Output is correct
6 Correct 2950 ms 479164 KB Output is correct
7 Correct 3740 ms 479680 KB Output is correct
8 Correct 3 ms 1596 KB Output is correct
9 Correct 385 ms 61892 KB Output is correct
10 Correct 330 ms 62104 KB Output is correct
11 Correct 364 ms 61856 KB Output is correct
12 Correct 316 ms 61872 KB Output is correct
13 Correct 355 ms 61988 KB Output is correct
14 Correct 645 ms 61964 KB Output is correct
15 Correct 306 ms 61752 KB Output is correct
16 Correct 281 ms 61896 KB Output is correct
17 Correct 445 ms 61724 KB Output is correct
18 Correct 2312 ms 62000 KB Output is correct
19 Correct 2423 ms 61964 KB Output is correct
20 Correct 973 ms 61972 KB Output is correct
21 Correct 4 ms 1516 KB Output is correct
22 Correct 327 ms 61788 KB Output is correct
23 Correct 378 ms 61872 KB Output is correct
24 Correct 313 ms 61696 KB Output is correct
25 Correct 321 ms 61772 KB Output is correct
26 Correct 406 ms 61964 KB Output is correct
27 Correct 372 ms 61744 KB Output is correct
28 Correct 280 ms 61868 KB Output is correct
29 Correct 937 ms 61848 KB Output is correct
30 Correct 2457 ms 61728 KB Output is correct
31 Correct 1141 ms 61992 KB Output is correct
32 Correct 348 ms 61164 KB Output is correct
33 Correct 422 ms 61860 KB Output is correct
34 Correct 315 ms 61900 KB Output is correct
35 Correct 343 ms 61488 KB Output is correct
36 Correct 405 ms 61740 KB Output is correct
37 Correct 420 ms 61676 KB Output is correct
38 Correct 425 ms 61644 KB Output is correct
39 Correct 941 ms 61736 KB Output is correct
40 Correct 555 ms 61712 KB Output is correct
41 Correct 858 ms 61392 KB Output is correct
42 Correct 563 ms 61568 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 3558 ms 479176 KB Output is correct
46 Correct 2416 ms 479292 KB Output is correct
47 Correct 2406 ms 479296 KB Output is correct
48 Correct 2424 ms 479172 KB Output is correct
49 Correct 3910 ms 479172 KB Output is correct
50 Correct 2495 ms 479180 KB Output is correct
51 Correct 2364 ms 479172 KB Output is correct
52 Correct 2523 ms 479296 KB Output is correct
53 Correct 5324 ms 479296 KB Output is correct
54 Correct 2873 ms 480836 KB Output is correct
55 Correct 3488 ms 480728 KB Output is correct
56 Correct 4358 ms 480792 KB Output is correct
57 Correct 4215 ms 480712 KB Output is correct
58 Correct 4263 ms 480840 KB Output is correct
59 Correct 4365 ms 480780 KB Output is correct
60 Correct 5930 ms 480932 KB Output is correct
61 Correct 5289 ms 486856 KB Output is correct