oj.uz

Submission #623424

# Submission time Handle Problem Language Result Execution time Memory
623424 2022-08-05T14:54:31 Z tinjyu Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4786 ms 1397932 KB 
#include "dungeons.h"
#include <vector>
#include <iostream>
using namespace std;
int cnt=0;
 
int n,s[1000005],p[1000005],l[1000005],w[1000005];
 
int step[400005][7][25];
long long int d[400005][7][25];
long long int mx[400005][7][25];
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N;
    for(int i=0;i<n;i++)s[i]=S[i];
    for(int i=0;i<n;i++)p[i]=P[i];
    for(int i=0;i<n;i++)w[i]=W[i];
    for(int i=0;i<n;i++)l[i]=L[i];
 
    long long int b=1;
    for(int bits=0;bits<5;bits++)
    {
        for(int i=0;i<n;i++)
        {
            if(s[i]>b)
            {
                step[i][bits][0]=l[i];
                mx[i][bits][0]=s[i];
                d[i][bits][0]=p[i];
            }
            else 
            {
                step[i][bits][0]=W[i];
                mx[i][bits][0]=1e18;
                d[i][bits][0]=S[i];
            }
        }
        for(int len=1;len<24;len++)
        {
            for(int i=0;i<n;i++)
            {
                long long int ti=2,now=i;
                mx[i][bits][len]=1e18;
                while(ti--)
                {
                    if(now==n)break;
                    mx[i][bits][len]=min(mx[i][bits][len],mx[now][bits][len-1]-d[i][bits][len]);
                    d[i][bits][len]+=d[now][bits][len-1];
                    step[i][bits][len]=step[now][bits][len-1];
                    now=step[i][bits][len];
                }
            }
        }
        b*=64;
    }
    return;
}
 
long long simulate(int x,int Z) {
    //cnt++;
    //if(cnt%1000==0)cout<<x<<" "<<Z<<endl;
    int now=x;
    long long int z=Z;
    long long int b=1;
    for(int bits=0;bits<5;bits++)
    {
        if(bits!=4 && b*64<=z)
        {
            b*=64;
            continue;
        }
        for(int len=23;len>=0;len--)
        {
            long long int count=0;
            
            while(z<mx[now][bits][len])
            {
                count++;
                //cout<<b<<" "<<bits<<" "<<now<<" "<<z<<" "<<mx[now][bits][len]<<" "<<len<<" "<<count<<" "<<s[now]<<" "<<p[now]<<" "<<w[now]<<" "<<l[now]<<endl;
                z+=d[now][bits][len];
                now=step[now][bits][len];
                //cout<<b<<" "<<bits<<" "<<now<<" "<<z<<" "<<mx[now][bits][len]<<" "<<len<<" "<<count<<" "<<s[now]<<" "<<p[now]<<" "<<w[now]<<" "<<l[now]<<endl;
                if(now==n)break;
            }
            if(now==n)break;
        }
        if(now==n)break;
        z+=s[now];
        now=w[now];
        if(now==n)break;
        //cout<<now<<" "<<z<<endl;
        b*=64;
        if(z<b)
        {
            b/=64;
            bits--;
        }
    }
    //system("pause");
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 5 ms 7188 KB Output is correct
4 Correct 304 ms 173900 KB Output is correct
5 Correct 6 ms 7252 KB Output is correct
6 Correct 278 ms 173936 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 2421 ms 1389780 KB Output is correct
3 Correct 2433 ms 1389804 KB Output is correct
4 Correct 2471 ms 1389888 KB Output is correct
5 Correct 2367 ms 1389896 KB Output is correct
6 Correct 2585 ms 1389780 KB Output is correct
7 Correct 2429 ms 1389756 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 343 ms 174684 KB Output is correct
3 Correct 317 ms 174820 KB Output is correct
4 Correct 271 ms 174728 KB Output is correct
5 Correct 402 ms 174732 KB Output is correct
6 Correct 314 ms 174724 KB Output is correct
7 Correct 351 ms 174752 KB Output is correct
8 Correct 289 ms 174732 KB Output is correct
9 Correct 278 ms 174836 KB Output is correct
10 Correct 312 ms 174684 KB Output is correct
11 Correct 338 ms 174884 KB Output is correct
12 Correct 464 ms 174832 KB Output is correct
13 Correct 376 ms 174728 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 343 ms 174684 KB Output is correct
3 Correct 317 ms 174820 KB Output is correct
4 Correct 271 ms 174728 KB Output is correct
5 Correct 402 ms 174732 KB Output is correct
6 Correct 314 ms 174724 KB Output is correct
7 Correct 351 ms 174752 KB Output is correct
8 Correct 289 ms 174732 KB Output is correct
9 Correct 278 ms 174836 KB Output is correct
10 Correct 312 ms 174684 KB Output is correct
11 Correct 338 ms 174884 KB Output is correct
12 Correct 464 ms 174832 KB Output is correct
13 Correct 376 ms 174728 KB Output is correct
14 Correct 3 ms 3796 KB Output is correct
15 Correct 314 ms 174720 KB Output is correct
16 Correct 336 ms 174796 KB Output is correct
17 Correct 319 ms 174616 KB Output is correct
18 Correct 327 ms 174820 KB Output is correct
19 Correct 372 ms 174724 KB Output is correct
20 Correct 312 ms 174668 KB Output is correct
21 Correct 376 ms 174708 KB Output is correct
22 Correct 504 ms 174728 KB Output is correct
23 Correct 381 ms 174672 KB Output is correct
24 Correct 498 ms 174732 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 343 ms 174684 KB Output is correct
3 Correct 317 ms 174820 KB Output is correct
4 Correct 271 ms 174728 KB Output is correct
5 Correct 402 ms 174732 KB Output is correct
6 Correct 314 ms 174724 KB Output is correct
7 Correct 351 ms 174752 KB Output is correct
8 Correct 289 ms 174732 KB Output is correct
9 Correct 278 ms 174836 KB Output is correct
10 Correct 312 ms 174684 KB Output is correct
11 Correct 338 ms 174884 KB Output is correct
12 Correct 464 ms 174832 KB Output is correct
13 Correct 376 ms 174728 KB Output is correct
14 Correct 3 ms 3796 KB Output is correct
15 Correct 314 ms 174720 KB Output is correct
16 Correct 336 ms 174796 KB Output is correct
17 Correct 319 ms 174616 KB Output is correct
18 Correct 327 ms 174820 KB Output is correct
19 Correct 372 ms 174724 KB Output is correct
20 Correct 312 ms 174668 KB Output is correct
21 Correct 376 ms 174708 KB Output is correct
22 Correct 504 ms 174728 KB Output is correct
23 Correct 381 ms 174672 KB Output is correct
24 Correct 498 ms 174732 KB Output is correct
25 Correct 310 ms 174004 KB Output is correct
26 Correct 315 ms 174724 KB Output is correct
27 Correct 374 ms 174728 KB Output is correct
28 Correct 320 ms 174820 KB Output is correct
29 Correct 348 ms 174728 KB Output is correct
30 Correct 394 ms 174856 KB Output is correct
31 Correct 377 ms 174844 KB Output is correct
32 Correct 540 ms 174856 KB Output is correct
33 Correct 858 ms 174656 KB Output is correct
34 Correct 1022 ms 174652 KB Output is correct
35 Correct 693 ms 174672 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 2421 ms 1389780 KB Output is correct
3 Correct 2433 ms 1389804 KB Output is correct
4 Correct 2471 ms 1389888 KB Output is correct
5 Correct 2367 ms 1389896 KB Output is correct
6 Correct 2585 ms 1389780 KB Output is correct
7 Correct 2429 ms 1389756 KB Output is correct
8 Correct 3 ms 3796 KB Output is correct
9 Correct 343 ms 174684 KB Output is correct
10 Correct 317 ms 174820 KB Output is correct
11 Correct 271 ms 174728 KB Output is correct
12 Correct 402 ms 174732 KB Output is correct
13 Correct 314 ms 174724 KB Output is correct
14 Correct 351 ms 174752 KB Output is correct
15 Correct 289 ms 174732 KB Output is correct
16 Correct 278 ms 174836 KB Output is correct
17 Correct 312 ms 174684 KB Output is correct
18 Correct 338 ms 174884 KB Output is correct
19 Correct 464 ms 174832 KB Output is correct
20 Correct 376 ms 174728 KB Output is correct
21 Correct 3 ms 3796 KB Output is correct
22 Correct 314 ms 174720 KB Output is correct
23 Correct 336 ms 174796 KB Output is correct
24 Correct 319 ms 174616 KB Output is correct
25 Correct 327 ms 174820 KB Output is correct
26 Correct 372 ms 174724 KB Output is correct
27 Correct 312 ms 174668 KB Output is correct
28 Correct 376 ms 174708 KB Output is correct
29 Correct 504 ms 174728 KB Output is correct
30 Correct 381 ms 174672 KB Output is correct
31 Correct 498 ms 174732 KB Output is correct
32 Correct 310 ms 174004 KB Output is correct
33 Correct 315 ms 174724 KB Output is correct
34 Correct 374 ms 174728 KB Output is correct
35 Correct 320 ms 174820 KB Output is correct
36 Correct 348 ms 174728 KB Output is correct
37 Correct 394 ms 174856 KB Output is correct
38 Correct 377 ms 174844 KB Output is correct
39 Correct 540 ms 174856 KB Output is correct
40 Correct 858 ms 174656 KB Output is correct
41 Correct 1022 ms 174652 KB Output is correct
42 Correct 693 ms 174672 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 3 ms 3796 KB Output is correct
45 Correct 2945 ms 1389776 KB Output is correct
46 Correct 2553 ms 1389788 KB Output is correct
47 Correct 2568 ms 1389784 KB Output is correct
48 Correct 2439 ms 1389768 KB Output is correct
49 Correct 3006 ms 1389832 KB Output is correct
50 Correct 2517 ms 1389780 KB Output is correct
51 Correct 2325 ms 1389760 KB Output is correct
52 Correct 2762 ms 1389780 KB Output is correct
53 Correct 4786 ms 1389784 KB Output is correct
54 Correct 3120 ms 1389700 KB Output is correct
55 Correct 3408 ms 1389752 KB Output is correct
56 Correct 4134 ms 1389776 KB Output is correct
57 Correct 4679 ms 1389780 KB Output is correct
58 Correct 4532 ms 1389864 KB Output is correct
59 Correct 4190 ms 1389892 KB Output is correct
60 Correct 4542 ms 1389820 KB Output is correct
61 Correct 4210 ms 1397932 KB Output is correct