oj.uz

Submission #887572

# Submission time Handle Problem Language Result Execution time Memory
887572 2023-12-14T18:39:57 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4009 ms 1905644 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=10,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 55 ms 380756 KB Output is correct
2 Correct 42 ms 380756 KB Output is correct
3 Correct 44 ms 387396 KB Output is correct
4 Correct 263 ms 572756 KB Output is correct
5 Correct 44 ms 387156 KB Output is correct
6 Correct 276 ms 572868 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 383112 KB Output is correct
2 Correct 3261 ms 1895568 KB Output is correct
3 Correct 2687 ms 1899692 KB Output is correct
4 Correct 2412 ms 1901164 KB Output is correct
5 Correct 2088 ms 1901780 KB Output is correct
6 Correct 2478 ms 1901096 KB Output is correct
7 Correct 2438 ms 1900136 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 383272 KB Output is correct
2 Correct 325 ms 574184 KB Output is correct
3 Correct 357 ms 574560 KB Output is correct
4 Correct 271 ms 573844 KB Output is correct
5 Correct 285 ms 573680 KB Output is correct
6 Correct 322 ms 573928 KB Output is correct
7 Correct 326 ms 573924 KB Output is correct
8 Correct 268 ms 573528 KB Output is correct
9 Correct 193 ms 573672 KB Output is correct
10 Correct 269 ms 573696 KB Output is correct
11 Correct 337 ms 573780 KB Output is correct
12 Correct 477 ms 573932 KB Output is correct
13 Correct 413 ms 573940 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 383272 KB Output is correct
2 Correct 325 ms 574184 KB Output is correct
3 Correct 357 ms 574560 KB Output is correct
4 Correct 271 ms 573844 KB Output is correct
5 Correct 285 ms 573680 KB Output is correct
6 Correct 322 ms 573928 KB Output is correct
7 Correct 326 ms 573924 KB Output is correct
8 Correct 268 ms 573528 KB Output is correct
9 Correct 193 ms 573672 KB Output is correct
10 Correct 269 ms 573696 KB Output is correct
11 Correct 337 ms 573780 KB Output is correct
12 Correct 477 ms 573932 KB Output is correct
13 Correct 413 ms 573940 KB Output is correct
14 Correct 43 ms 383128 KB Output is correct
15 Correct 321 ms 574148 KB Output is correct
16 Correct 323 ms 574400 KB Output is correct
17 Correct 326 ms 573800 KB Output is correct
18 Correct 328 ms 573776 KB Output is correct
19 Correct 348 ms 573852 KB Output is correct
20 Correct 368 ms 573560 KB Output is correct
21 Correct 367 ms 573864 KB Output is correct
22 Correct 336 ms 573796 KB Output is correct
23 Correct 344 ms 573924 KB Output is correct
24 Correct 481 ms 574032 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 383272 KB Output is correct
2 Correct 325 ms 574184 KB Output is correct
3 Correct 357 ms 574560 KB Output is correct
4 Correct 271 ms 573844 KB Output is correct
5 Correct 285 ms 573680 KB Output is correct
6 Correct 322 ms 573928 KB Output is correct
7 Correct 326 ms 573924 KB Output is correct
8 Correct 268 ms 573528 KB Output is correct
9 Correct 193 ms 573672 KB Output is correct
10 Correct 269 ms 573696 KB Output is correct
11 Correct 337 ms 573780 KB Output is correct
12 Correct 477 ms 573932 KB Output is correct
13 Correct 413 ms 573940 KB Output is correct
14 Correct 43 ms 383128 KB Output is correct
15 Correct 321 ms 574148 KB Output is correct
16 Correct 323 ms 574400 KB Output is correct
17 Correct 326 ms 573800 KB Output is correct
18 Correct 328 ms 573776 KB Output is correct
19 Correct 348 ms 573852 KB Output is correct
20 Correct 368 ms 573560 KB Output is correct
21 Correct 367 ms 573864 KB Output is correct
22 Correct 336 ms 573796 KB Output is correct
23 Correct 344 ms 573924 KB Output is correct
24 Correct 481 ms 574032 KB Output is correct
25 Correct 295 ms 573240 KB Output is correct
26 Correct 334 ms 574224 KB Output is correct
27 Correct 330 ms 573640 KB Output is correct
28 Correct 308 ms 573676 KB Output is correct
29 Correct 361 ms 574036 KB Output is correct
30 Correct 385 ms 573936 KB Output is correct
31 Correct 387 ms 573672 KB Output is correct
32 Correct 474 ms 573808 KB Output is correct
33 Correct 1255 ms 573808 KB Output is correct
34 Correct 1231 ms 573808 KB Output is correct
35 Correct 553 ms 573764 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 383112 KB Output is correct
2 Correct 3261 ms 1895568 KB Output is correct
3 Correct 2687 ms 1899692 KB Output is correct
4 Correct 2412 ms 1901164 KB Output is correct
5 Correct 2088 ms 1901780 KB Output is correct
6 Correct 2478 ms 1901096 KB Output is correct
7 Correct 2438 ms 1900136 KB Output is correct
8 Correct 45 ms 383272 KB Output is correct
9 Correct 325 ms 574184 KB Output is correct
10 Correct 357 ms 574560 KB Output is correct
11 Correct 271 ms 573844 KB Output is correct
12 Correct 285 ms 573680 KB Output is correct
13 Correct 322 ms 573928 KB Output is correct
14 Correct 326 ms 573924 KB Output is correct
15 Correct 268 ms 573528 KB Output is correct
16 Correct 193 ms 573672 KB Output is correct
17 Correct 269 ms 573696 KB Output is correct
18 Correct 337 ms 573780 KB Output is correct
19 Correct 477 ms 573932 KB Output is correct
20 Correct 413 ms 573940 KB Output is correct
21 Correct 43 ms 383128 KB Output is correct
22 Correct 321 ms 574148 KB Output is correct
23 Correct 323 ms 574400 KB Output is correct
24 Correct 326 ms 573800 KB Output is correct
25 Correct 328 ms 573776 KB Output is correct
26 Correct 348 ms 573852 KB Output is correct
27 Correct 368 ms 573560 KB Output is correct
28 Correct 367 ms 573864 KB Output is correct
29 Correct 336 ms 573796 KB Output is correct
30 Correct 344 ms 573924 KB Output is correct
31 Correct 481 ms 574032 KB Output is correct
32 Correct 295 ms 573240 KB Output is correct
33 Correct 334 ms 574224 KB Output is correct
34 Correct 330 ms 573640 KB Output is correct
35 Correct 308 ms 573676 KB Output is correct
36 Correct 361 ms 574036 KB Output is correct
37 Correct 385 ms 573936 KB Output is correct
38 Correct 387 ms 573672 KB Output is correct
39 Correct 474 ms 573808 KB Output is correct
40 Correct 1255 ms 573808 KB Output is correct
41 Correct 1231 ms 573808 KB Output is correct
42 Correct 553 ms 573764 KB Output is correct
43 Correct 43 ms 380920 KB Output is correct
44 Correct 43 ms 383216 KB Output is correct
45 Correct 2378 ms 1904380 KB Output is correct
46 Correct 2242 ms 1902200 KB Output is correct
47 Correct 2299 ms 1902288 KB Output is correct
48 Correct 2253 ms 1904112 KB Output is correct
49 Correct 2347 ms 1905644 KB Output is correct
50 Correct 2484 ms 1903720 KB Output is correct
51 Correct 2159 ms 1904104 KB Output is correct
52 Correct 2584 ms 1902532 KB Output is correct
53 Correct 3640 ms 1902940 KB Output is correct
54 Correct 3782 ms 1904040 KB Output is correct
55 Correct 3838 ms 1903212 KB Output is correct
56 Correct 3688 ms 1903508 KB Output is correct
57 Correct 3689 ms 1895548 KB Output is correct
58 Correct 3942 ms 1895548 KB Output is correct
59 Correct 4009 ms 1895544 KB Output is correct
60 Correct 3953 ms 1895552 KB Output is correct
61 Correct 3802 ms 1895548 KB Output is correct