oj.uz

Submission #879799

# Submission time Handle Problem Language Result Execution time Memory
879799 2023-11-28T07:06:48 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 1866584 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=6;
int nxt[400001][24][sz+1];
long long mx[400001][24][sz+1],mn[400001][24][sz+1],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()*15);
    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];
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
            }
        nxt[i][0][sz]=w[i];
        for (int j=0;j<=sz;j++)
            mx[i][0][j]=mn[i][0][j]=s[i];
        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];
                mx[i][j][k]=max(mx[i][j-1][k],mx[u][j-1][k]-sum[i][j-1][k]);
                mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-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;
    long long z=Z;
    while (nxt[x][0][0]!=-1){
        int j=(b?upper_bound(ve.begin(),ve.end(),z)-ve.begin()-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][j])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 269392 KB Output is correct
2 Correct 32 ms 269500 KB Output is correct
3 Correct 36 ms 277944 KB Output is correct
4 Correct 267 ms 469572 KB Output is correct
5 Correct 34 ms 277844 KB Output is correct
6 Correct 253 ms 469332 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273744 KB Output is correct
2 Correct 3417 ms 1858048 KB Output is correct
3 Correct 3084 ms 1864872 KB Output is correct
4 Correct 2644 ms 1866408 KB Output is correct
5 Correct 2545 ms 1866584 KB Output is correct
6 Correct 3118 ms 1864784 KB Output is correct
7 Correct 2606 ms 1862828 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273844 KB Output is correct
2 Correct 317 ms 471116 KB Output is correct
3 Correct 330 ms 471112 KB Output is correct
4 Correct 263 ms 470592 KB Output is correct
5 Correct 272 ms 470360 KB Output is correct
6 Correct 326 ms 470540 KB Output is correct
7 Correct 319 ms 470612 KB Output is correct
8 Correct 269 ms 470356 KB Output is correct
9 Correct 213 ms 470352 KB Output is correct
10 Correct 275 ms 470096 KB Output is correct
11 Correct 329 ms 470596 KB Output is correct
12 Correct 495 ms 470616 KB Output is correct
13 Correct 421 ms 470660 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273844 KB Output is correct
2 Correct 317 ms 471116 KB Output is correct
3 Correct 330 ms 471112 KB Output is correct
4 Correct 263 ms 470592 KB Output is correct
5 Correct 272 ms 470360 KB Output is correct
6 Correct 326 ms 470540 KB Output is correct
7 Correct 319 ms 470612 KB Output is correct
8 Correct 269 ms 470356 KB Output is correct
9 Correct 213 ms 470352 KB Output is correct
10 Correct 275 ms 470096 KB Output is correct
11 Correct 329 ms 470596 KB Output is correct
12 Correct 495 ms 470616 KB Output is correct
13 Correct 421 ms 470660 KB Output is correct
14 Correct 34 ms 273748 KB Output is correct
15 Correct 460 ms 470976 KB Output is correct
16 Correct 320 ms 470952 KB Output is correct
17 Correct 293 ms 470440 KB Output is correct
18 Correct 285 ms 470592 KB Output is correct
19 Correct 334 ms 470604 KB Output is correct
20 Correct 327 ms 470608 KB Output is correct
21 Correct 302 ms 470612 KB Output is correct
22 Execution timed out 7005 ms 470352 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273844 KB Output is correct
2 Correct 317 ms 471116 KB Output is correct
3 Correct 330 ms 471112 KB Output is correct
4 Correct 263 ms 470592 KB Output is correct
5 Correct 272 ms 470360 KB Output is correct
6 Correct 326 ms 470540 KB Output is correct
7 Correct 319 ms 470612 KB Output is correct
8 Correct 269 ms 470356 KB Output is correct
9 Correct 213 ms 470352 KB Output is correct
10 Correct 275 ms 470096 KB Output is correct
11 Correct 329 ms 470596 KB Output is correct
12 Correct 495 ms 470616 KB Output is correct
13 Correct 421 ms 470660 KB Output is correct
14 Correct 34 ms 273748 KB Output is correct
15 Correct 460 ms 470976 KB Output is correct
16 Correct 320 ms 470952 KB Output is correct
17 Correct 293 ms 470440 KB Output is correct
18 Correct 285 ms 470592 KB Output is correct
19 Correct 334 ms 470604 KB Output is correct
20 Correct 327 ms 470608 KB Output is correct
21 Correct 302 ms 470612 KB Output is correct
22 Execution timed out 7005 ms 470352 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273744 KB Output is correct
2 Correct 3417 ms 1858048 KB Output is correct
3 Correct 3084 ms 1864872 KB Output is correct
4 Correct 2644 ms 1866408 KB Output is correct
5 Correct 2545 ms 1866584 KB Output is correct
6 Correct 3118 ms 1864784 KB Output is correct
7 Correct 2606 ms 1862828 KB Output is correct
8 Correct 33 ms 273844 KB Output is correct
9 Correct 317 ms 471116 KB Output is correct
10 Correct 330 ms 471112 KB Output is correct
11 Correct 263 ms 470592 KB Output is correct
12 Correct 272 ms 470360 KB Output is correct
13 Correct 326 ms 470540 KB Output is correct
14 Correct 319 ms 470612 KB Output is correct
15 Correct 269 ms 470356 KB Output is correct
16 Correct 213 ms 470352 KB Output is correct
17 Correct 275 ms 470096 KB Output is correct
18 Correct 329 ms 470596 KB Output is correct
19 Correct 495 ms 470616 KB Output is correct
20 Correct 421 ms 470660 KB Output is correct
21 Correct 34 ms 273748 KB Output is correct
22 Correct 460 ms 470976 KB Output is correct
23 Correct 320 ms 470952 KB Output is correct
24 Correct 293 ms 470440 KB Output is correct
25 Correct 285 ms 470592 KB Output is correct
26 Correct 334 ms 470604 KB Output is correct
27 Correct 327 ms 470608 KB Output is correct
28 Correct 302 ms 470612 KB Output is correct
29 Execution timed out 7005 ms 470352 KB Time limit exceeded
30 Halted 0 ms 0 KB -