oj.uz

Submission #887566

# Submission time Handle Problem Language Result Execution time Memory
887566 2023-12-14T18:37:00 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5395 ms 1907188 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=6,sz=9;
const long long INF=1e18;
int nxt[400001][24][sz+1];
long long mx[400001][24],mn[400001][24][sz],sum[400001][24][sz+1];
vector <int> S,P,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    S=s;
    P=p;
    for (int i=1;i<sz;i++)
        ve.push_back(ve.back()*base);
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<sz;j++)
            if (s[i]<=ve[j]){
                nxt[i][0][j]=w[i];
                sum[i][0][j]=s[i];
                mn[i][0][j]=INF;
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
                mn[i][0][j]=s[i];
            }
        nxt[i][0][sz]=w[i];
        mx[i][0]=sum[i][0][sz]=s[i];
    }
    for (int j=1;j<24;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<=sz;k++){
                if (nxt[i][j-1][k]==-1)
                    continue;
                int u=nxt[i][j-1][k];
                nxt[i][j][k]=nxt[u][j-1][k];
                if (k<sz)
                    mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                else
                    mx[i][j]=max(mx[i][j-1],mx[u][j-1]-sum[i][j-1][k]);
                sum[i][j][k]=sum[i][j-1][k]+sum[u][j-1][k];
            }
    }
}
long long simulate(int x, int Z){
    int b=0,cur=0;
    long long z=Z;
    while (nxt[x][0][0]!=-1){
        while (cur<ve.size()&&ve[cur]<=z)
            cur++;
        int j=(b?cur-1:sz);
        for (int i=23;i>=0;i--)
            if (nxt[x][i][j]!=-1)
                if ((b&&z<mn[x][i][j])||(!b&&z>=mx[x][i])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
	return z;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (cur<ve.size()&&ve[cur]<=z)
      |                ~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 380760 KB Output is correct
2 Correct 42 ms 380916 KB Output is correct
3 Correct 45 ms 387192 KB Output is correct
4 Correct 302 ms 570920 KB Output is correct
5 Correct 45 ms 387268 KB Output is correct
6 Correct 287 ms 570776 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 383056 KB Output is correct
2 Correct 3494 ms 1895564 KB Output is correct
3 Correct 3371 ms 1898688 KB Output is correct
4 Correct 3523 ms 1899932 KB Output is correct
5 Correct 2754 ms 1901172 KB Output is correct
6 Correct 3333 ms 1900768 KB Output is correct
7 Correct 3335 ms 1900396 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 383268 KB Output is correct
2 Correct 350 ms 574196 KB Output is correct
3 Correct 352 ms 574432 KB Output is correct
4 Correct 292 ms 573800 KB Output is correct
5 Correct 298 ms 573676 KB Output is correct
6 Correct 352 ms 573928 KB Output is correct
7 Correct 347 ms 573856 KB Output is correct
8 Correct 296 ms 573440 KB Output is correct
9 Correct 231 ms 573584 KB Output is correct
10 Correct 283 ms 573412 KB Output is correct
11 Correct 336 ms 573860 KB Output is correct
12 Correct 521 ms 573820 KB Output is correct
13 Correct 444 ms 573924 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 383268 KB Output is correct
2 Correct 350 ms 574196 KB Output is correct
3 Correct 352 ms 574432 KB Output is correct
4 Correct 292 ms 573800 KB Output is correct
5 Correct 298 ms 573676 KB Output is correct
6 Correct 352 ms 573928 KB Output is correct
7 Correct 347 ms 573856 KB Output is correct
8 Correct 296 ms 573440 KB Output is correct
9 Correct 231 ms 573584 KB Output is correct
10 Correct 283 ms 573412 KB Output is correct
11 Correct 336 ms 573860 KB Output is correct
12 Correct 521 ms 573820 KB Output is correct
13 Correct 444 ms 573924 KB Output is correct
14 Correct 45 ms 383120 KB Output is correct
15 Correct 351 ms 574080 KB Output is correct
16 Correct 355 ms 574168 KB Output is correct
17 Correct 366 ms 573916 KB Output is correct
18 Correct 382 ms 573804 KB Output is correct
19 Correct 351 ms 573924 KB Output is correct
20 Correct 412 ms 573644 KB Output is correct
21 Correct 391 ms 573796 KB Output is correct
22 Correct 340 ms 573776 KB Output is correct
23 Correct 372 ms 573928 KB Output is correct
24 Correct 521 ms 573932 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 383268 KB Output is correct
2 Correct 350 ms 574196 KB Output is correct
3 Correct 352 ms 574432 KB Output is correct
4 Correct 292 ms 573800 KB Output is correct
5 Correct 298 ms 573676 KB Output is correct
6 Correct 352 ms 573928 KB Output is correct
7 Correct 347 ms 573856 KB Output is correct
8 Correct 296 ms 573440 KB Output is correct
9 Correct 231 ms 573584 KB Output is correct
10 Correct 283 ms 573412 KB Output is correct
11 Correct 336 ms 573860 KB Output is correct
12 Correct 521 ms 573820 KB Output is correct
13 Correct 444 ms 573924 KB Output is correct
14 Correct 45 ms 383120 KB Output is correct
15 Correct 351 ms 574080 KB Output is correct
16 Correct 355 ms 574168 KB Output is correct
17 Correct 366 ms 573916 KB Output is correct
18 Correct 382 ms 573804 KB Output is correct
19 Correct 351 ms 573924 KB Output is correct
20 Correct 412 ms 573644 KB Output is correct
21 Correct 391 ms 573796 KB Output is correct
22 Correct 340 ms 573776 KB Output is correct
23 Correct 372 ms 573928 KB Output is correct
24 Correct 521 ms 573932 KB Output is correct
25 Correct 303 ms 573248 KB Output is correct
26 Correct 352 ms 574300 KB Output is correct
27 Correct 325 ms 573760 KB Output is correct
28 Correct 361 ms 573756 KB Output is correct
29 Correct 374 ms 574032 KB Output is correct
30 Correct 409 ms 573972 KB Output is correct
31 Correct 413 ms 573780 KB Output is correct
32 Correct 500 ms 573804 KB Output is correct
33 Correct 1043 ms 573932 KB Output is correct
34 Correct 1303 ms 573804 KB Output is correct
35 Correct 563 ms 573800 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 383056 KB Output is correct
2 Correct 3494 ms 1895564 KB Output is correct
3 Correct 3371 ms 1898688 KB Output is correct
4 Correct 3523 ms 1899932 KB Output is correct
5 Correct 2754 ms 1901172 KB Output is correct
6 Correct 3333 ms 1900768 KB Output is correct
7 Correct 3335 ms 1900396 KB Output is correct
8 Correct 47 ms 383268 KB Output is correct
9 Correct 350 ms 574196 KB Output is correct
10 Correct 352 ms 574432 KB Output is correct
11 Correct 292 ms 573800 KB Output is correct
12 Correct 298 ms 573676 KB Output is correct
13 Correct 352 ms 573928 KB Output is correct
14 Correct 347 ms 573856 KB Output is correct
15 Correct 296 ms 573440 KB Output is correct
16 Correct 231 ms 573584 KB Output is correct
17 Correct 283 ms 573412 KB Output is correct
18 Correct 336 ms 573860 KB Output is correct
19 Correct 521 ms 573820 KB Output is correct
20 Correct 444 ms 573924 KB Output is correct
21 Correct 45 ms 383120 KB Output is correct
22 Correct 351 ms 574080 KB Output is correct
23 Correct 355 ms 574168 KB Output is correct
24 Correct 366 ms 573916 KB Output is correct
25 Correct 382 ms 573804 KB Output is correct
26 Correct 351 ms 573924 KB Output is correct
27 Correct 412 ms 573644 KB Output is correct
28 Correct 391 ms 573796 KB Output is correct
29 Correct 340 ms 573776 KB Output is correct
30 Correct 372 ms 573928 KB Output is correct
31 Correct 521 ms 573932 KB Output is correct
32 Correct 303 ms 573248 KB Output is correct
33 Correct 352 ms 574300 KB Output is correct
34 Correct 325 ms 573760 KB Output is correct
35 Correct 361 ms 573756 KB Output is correct
36 Correct 374 ms 574032 KB Output is correct
37 Correct 409 ms 573972 KB Output is correct
38 Correct 413 ms 573780 KB Output is correct
39 Correct 500 ms 573804 KB Output is correct
40 Correct 1043 ms 573932 KB Output is correct
41 Correct 1303 ms 573804 KB Output is correct
42 Correct 563 ms 573800 KB Output is correct
43 Correct 44 ms 380880 KB Output is correct
44 Correct 45 ms 383060 KB Output is correct
45 Correct 4616 ms 1895572 KB Output is correct
46 Correct 3087 ms 1902668 KB Output is correct
47 Correct 3919 ms 1902408 KB Output is correct
48 Correct 2632 ms 1905232 KB Output is correct
49 Correct 3268 ms 1907188 KB Output is correct
50 Correct 3184 ms 1904692 KB Output is correct
51 Correct 2508 ms 1905136 KB Output is correct
52 Correct 3194 ms 1902828 KB Output is correct
53 Correct 4828 ms 1903452 KB Output is correct
54 Correct 4181 ms 1904748 KB Output is correct
55 Correct 4209 ms 1903684 KB Output is correct
56 Correct 4991 ms 1903152 KB Output is correct
57 Correct 5353 ms 1903800 KB Output is correct
58 Correct 5031 ms 1904340 KB Output is correct
59 Correct 5395 ms 1904620 KB Output is correct
60 Correct 4697 ms 1903864 KB Output is correct
61 Correct 4529 ms 1903312 KB Output is correct