oj.uz

Submission #879787

# Submission time Handle Problem Language Result Execution time Memory
879787 2023-11-28T06:26:42 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 551256 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=24;
int nxt[400001][sz][2];
long long mx[400001][sz][2],mn[400001][sz][2],sum[400001][sz][2];
vector <int> S,P;
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    S=s;
    P=p;
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        nxt[i][0][0]=w[i];
        nxt[i][0][1]=l[i];
        for (int j=0;j<2;j++)
            mx[i][0][j]=mn[i][0][j]=s[i];
        sum[i][0][0]=s[i];
        sum[i][0][1]=p[i];
    }
    for (int j=1;j<sz;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<2;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 (true){
        if (nxt[x][0][0]==-1)
            return z;
        for (int i=sz-1;i>=0;i--)
            if (nxt[x][i][b]!=-1)
                if ((b&&z<mn[x][i][b])||(!b&&z>=mx[x][i][b])){
                    z+=sum[x][i][b];
                    x=nxt[x][i][b];
                }
        b^=1;
    }
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 80988 KB Output is correct
2 Correct 10 ms 80984 KB Output is correct
3 Correct 11 ms 83288 KB Output is correct
4 Correct 67 ms 141552 KB Output is correct
5 Correct 10 ms 83292 KB Output is correct
6 Correct 64 ms 141720 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 83288 KB Output is correct
2 Correct 829 ms 549804 KB Output is correct
3 Correct 777 ms 549824 KB Output is correct
4 Correct 709 ms 551108 KB Output is correct
5 Correct 527 ms 551256 KB Output is correct
6 Correct 657 ms 550068 KB Output is correct
7 Correct 650 ms 548180 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 83288 KB Output is correct
2 Correct 91 ms 142920 KB Output is correct
3 Correct 114 ms 143168 KB Output is correct
4 Correct 106 ms 142416 KB Output is correct
5 Correct 98 ms 142400 KB Output is correct
6 Correct 91 ms 142660 KB Output is correct
7 Correct 99 ms 142872 KB Output is correct
8 Correct 104 ms 142164 KB Output is correct
9 Correct 84 ms 142172 KB Output is correct
10 Correct 102 ms 142168 KB Output is correct
11 Correct 105 ms 142680 KB Output is correct
12 Correct 159 ms 142656 KB Output is correct
13 Correct 124 ms 142428 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 83288 KB Output is correct
2 Correct 91 ms 142920 KB Output is correct
3 Correct 114 ms 143168 KB Output is correct
4 Correct 106 ms 142416 KB Output is correct
5 Correct 98 ms 142400 KB Output is correct
6 Correct 91 ms 142660 KB Output is correct
7 Correct 99 ms 142872 KB Output is correct
8 Correct 104 ms 142164 KB Output is correct
9 Correct 84 ms 142172 KB Output is correct
10 Correct 102 ms 142168 KB Output is correct
11 Correct 105 ms 142680 KB Output is correct
12 Correct 159 ms 142656 KB Output is correct
13 Correct 124 ms 142428 KB Output is correct
14 Correct 10 ms 83544 KB Output is correct
15 Correct 196 ms 142760 KB Output is correct
16 Correct 91 ms 142916 KB Output is correct
17 Correct 100 ms 142400 KB Output is correct
18 Correct 96 ms 142420 KB Output is correct
19 Correct 97 ms 142652 KB Output is correct
20 Correct 115 ms 142328 KB Output is correct
21 Correct 109 ms 142512 KB Output is correct
22 Execution timed out 7022 ms 142456 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 83288 KB Output is correct
2 Correct 91 ms 142920 KB Output is correct
3 Correct 114 ms 143168 KB Output is correct
4 Correct 106 ms 142416 KB Output is correct
5 Correct 98 ms 142400 KB Output is correct
6 Correct 91 ms 142660 KB Output is correct
7 Correct 99 ms 142872 KB Output is correct
8 Correct 104 ms 142164 KB Output is correct
9 Correct 84 ms 142172 KB Output is correct
10 Correct 102 ms 142168 KB Output is correct
11 Correct 105 ms 142680 KB Output is correct
12 Correct 159 ms 142656 KB Output is correct
13 Correct 124 ms 142428 KB Output is correct
14 Correct 10 ms 83544 KB Output is correct
15 Correct 196 ms 142760 KB Output is correct
16 Correct 91 ms 142916 KB Output is correct
17 Correct 100 ms 142400 KB Output is correct
18 Correct 96 ms 142420 KB Output is correct
19 Correct 97 ms 142652 KB Output is correct
20 Correct 115 ms 142328 KB Output is correct
21 Correct 109 ms 142512 KB Output is correct
22 Execution timed out 7022 ms 142456 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 83288 KB Output is correct
2 Correct 829 ms 549804 KB Output is correct
3 Correct 777 ms 549824 KB Output is correct
4 Correct 709 ms 551108 KB Output is correct
5 Correct 527 ms 551256 KB Output is correct
6 Correct 657 ms 550068 KB Output is correct
7 Correct 650 ms 548180 KB Output is correct
8 Correct 10 ms 83288 KB Output is correct
9 Correct 91 ms 142920 KB Output is correct
10 Correct 114 ms 143168 KB Output is correct
11 Correct 106 ms 142416 KB Output is correct
12 Correct 98 ms 142400 KB Output is correct
13 Correct 91 ms 142660 KB Output is correct
14 Correct 99 ms 142872 KB Output is correct
15 Correct 104 ms 142164 KB Output is correct
16 Correct 84 ms 142172 KB Output is correct
17 Correct 102 ms 142168 KB Output is correct
18 Correct 105 ms 142680 KB Output is correct
19 Correct 159 ms 142656 KB Output is correct
20 Correct 124 ms 142428 KB Output is correct
21 Correct 10 ms 83544 KB Output is correct
22 Correct 196 ms 142760 KB Output is correct
23 Correct 91 ms 142916 KB Output is correct
24 Correct 100 ms 142400 KB Output is correct
25 Correct 96 ms 142420 KB Output is correct
26 Correct 97 ms 142652 KB Output is correct
27 Correct 115 ms 142328 KB Output is correct
28 Correct 109 ms 142512 KB Output is correct
29 Execution timed out 7022 ms 142456 KB Time limit exceeded
30 Halted 0 ms 0 KB -