oj.uz

Submission #745307

# Submission time Handle Problem Language Result Execution time Memory
745307 2023-05-19T19:40:22 Z arthur_nascimento Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2443 ms 865232 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
 
#define lg 7
#define maxn 400400
#define inf (1e9)
#define debug 
#define ll long long
 
int jmp[lg][19][maxn];
ll inc[lg][19][maxn];
int least[lg][19][maxn];
 
vector<int> strength, inc_lose, go_win, go_lose;
 
int n;
 
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
 
	//for(int i=0;i<N;i++) if(s[i] != 642842 ) printf("! %d -> %d %d, %d %d\n",i,w[i],l[i],s[i],p[i]);
	
	n = N;
	strength = s;
	inc_lose = p;
	go_win = w;
	go_lose = l;
 
	strength.pb(0);
	inc_lose.pb(0);
	go_win.pb(n);
	go_lose.pb(n);
 
	debug("ini!\n");
 
	for(int k=0;k<lg;k++){
 
		for(int i=0;i<n;i++){
 
			if(strength[i] <= (1<<(4*k)))
				jmp[k][0][i] = go_win[i],
				inc[k][0][i] = strength[i],
				least[k][0][i] = inf;
			else
				jmp[k][0][i] = go_lose[i],
				inc[k][0][i] = inc_lose[i],
				least[k][0][i] = strength[i];
 
			if(k == 0)
				debug("%d -> %d\n",i,jmp[k][0][i]);
 
			if(jmp[k][0][i] == n)
				least[k][0][i] = -1;
			
		}
 
		for(int j=1;j<19;j++)
			for(int i=0;i<n;i++){
 
				jmp[k][j][i] = jmp[k][j-1][jmp[k][j-1][i]],
				inc[k][j][i] = inc[k][j-1][i] + inc[k][j-1][ jmp[k][j-1][i] ] ,
				least[k][j][i] = max(0ll, min( (ll)least[k][j-1][i], least[k][j-1][ jmp[k][j-1][i] ] - inc[k][j-1][i] ));
             	
              	if(least[k][j-1][i] > 1e8 && least[k][j-1][ jmp[k][j-1][i] ] > 1e8)
                  	least[k][j][i] = 1e9;
              	
            }
 
	}
 
	return;
}
 
long long simulate(int x, int z0) {
 
	ll z = z0; 
	
	while(x < n){
 
		ll aux = z;
		int k = 0;
		while(aux > 1)
			aux /= 2, k++;
 
        k /= 4;
		k = min(k,6);
 
		debug("x %d z %d k %d\n",x,z,k);
 
		//for(int i=0;i<n;i++)
			//debug("k %d i %d -> %d\n",k,i,jmp[k][0][i]);
 
		debug("\n");
 
		for(int j=18;j>=0;j--)
			if(least[k][j][x] > z || least[k][j][x] > 1e8){
 
				z += inc[k][j][x];
				debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
				x = jmp[k][j][x];
				
 
			}
		debug("z %d x %d stx %d\n",z,x,strength[x]);
	//	assert(z >= strength[x]);
		//if(!((strength[x] >= (1<<k) || go_win[x] == n))) return 0;
 
		if(z >= strength[x])
			z += strength[x],
			x = go_win[x];
		else
			z += inc_lose[x],
			x = go_lose[x];
 
	}
	//printf("ans %d\n",z);
 
	return z;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:36:8: warning: statement has no effect [-Wunused-value]
   36 |  debug("ini!\n");
      |       ~^~~~~~~~~
dungeons.cpp:52:11: warning: left operand of comma operator has no effect [-Wunused-value]
   52 |     debug("%d -> %d\n",i,jmp[k][0][i]);
      |           ^~~~~~~~~~~~
dungeons.cpp:52:37: warning: right operand of comma operator has no effect [-Wunused-value]
   52 |     debug("%d -> %d\n",i,jmp[k][0][i]);
      |                                     ^
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:90:9: warning: left operand of comma operator has no effect [-Wunused-value]
   90 |   debug("x %d z %d k %d\n",x,z,k);
      |         ^~~~~~~~~~~~~~~~~~
dungeons.cpp:90:30: warning: right operand of comma operator has no effect [-Wunused-value]
   90 |   debug("x %d z %d k %d\n",x,z,k);
      |                              ^
dungeons.cpp:90:32: warning: right operand of comma operator has no effect [-Wunused-value]
   90 |   debug("x %d z %d k %d\n",x,z,k);
      |                                ^
dungeons.cpp:95:9: warning: statement has no effect [-Wunused-value]
   95 |   debug("\n");
      |        ~^~~~~
dungeons.cpp:101:11: warning: left operand of comma operator has no effect [-Wunused-value]
  101 |     debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~
dungeons.cpp:101:43: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |     debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
      |                                           ^
dungeons.cpp:101:41: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |     debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
      |                                        ~^~~
dungeons.cpp:101:56: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |     debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
      |                                             ~~~~~~~~~~~^
dungeons.cpp:106:9: warning: left operand of comma operator has no effect [-Wunused-value]
  106 |   debug("z %d x %d stx %d\n",z,x,strength[x]);
      |         ^~~~~~~~~~~~~~~~~~~~
dungeons.cpp:106:32: warning: right operand of comma operator has no effect [-Wunused-value]
  106 |   debug("z %d x %d stx %d\n",z,x,strength[x]);
      |                                ^
dungeons.cpp:106:44: warning: right operand of comma operator has no effect [-Wunused-value]
  106 |   debug("z %d x %d stx %d\n",z,x,strength[x]);
      |                                            ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 84 ms 109592 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 85 ms 109564 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 629 ms 853700 KB Output is correct
3 Correct 643 ms 860408 KB Output is correct
4 Correct 649 ms 862032 KB Output is correct
5 Correct 704 ms 862060 KB Output is correct
6 Correct 658 ms 860504 KB Output is correct
7 Correct 683 ms 858624 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 130 ms 110288 KB Output is correct
3 Correct 122 ms 110284 KB Output is correct
4 Correct 106 ms 110396 KB Output is correct
5 Correct 104 ms 110372 KB Output is correct
6 Correct 177 ms 110292 KB Output is correct
7 Correct 323 ms 110272 KB Output is correct
8 Correct 122 ms 110316 KB Output is correct
9 Correct 117 ms 110356 KB Output is correct
10 Correct 121 ms 110268 KB Output is correct
11 Correct 140 ms 110296 KB Output is correct
12 Correct 1719 ms 110316 KB Output is correct
13 Correct 1741 ms 110344 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 130 ms 110288 KB Output is correct
3 Correct 122 ms 110284 KB Output is correct
4 Correct 106 ms 110396 KB Output is correct
5 Correct 104 ms 110372 KB Output is correct
6 Correct 177 ms 110292 KB Output is correct
7 Correct 323 ms 110272 KB Output is correct
8 Correct 122 ms 110316 KB Output is correct
9 Correct 117 ms 110356 KB Output is correct
10 Correct 121 ms 110268 KB Output is correct
11 Correct 140 ms 110296 KB Output is correct
12 Correct 1719 ms 110316 KB Output is correct
13 Correct 1741 ms 110344 KB Output is correct
14 Correct 3 ms 5332 KB Output is correct
15 Correct 111 ms 110376 KB Output is correct
16 Correct 127 ms 110428 KB Output is correct
17 Correct 112 ms 110308 KB Output is correct
18 Correct 107 ms 110304 KB Output is correct
19 Correct 165 ms 110340 KB Output is correct
20 Correct 130 ms 110268 KB Output is correct
21 Correct 136 ms 110368 KB Output is correct
22 Correct 148 ms 110360 KB Output is correct
23 Correct 129 ms 110276 KB Output is correct
24 Correct 337 ms 110396 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 130 ms 110288 KB Output is correct
3 Correct 122 ms 110284 KB Output is correct
4 Correct 106 ms 110396 KB Output is correct
5 Correct 104 ms 110372 KB Output is correct
6 Correct 177 ms 110292 KB Output is correct
7 Correct 323 ms 110272 KB Output is correct
8 Correct 122 ms 110316 KB Output is correct
9 Correct 117 ms 110356 KB Output is correct
10 Correct 121 ms 110268 KB Output is correct
11 Correct 140 ms 110296 KB Output is correct
12 Correct 1719 ms 110316 KB Output is correct
13 Correct 1741 ms 110344 KB Output is correct
14 Correct 3 ms 5332 KB Output is correct
15 Correct 111 ms 110376 KB Output is correct
16 Correct 127 ms 110428 KB Output is correct
17 Correct 112 ms 110308 KB Output is correct
18 Correct 107 ms 110304 KB Output is correct
19 Correct 165 ms 110340 KB Output is correct
20 Correct 130 ms 110268 KB Output is correct
21 Correct 136 ms 110368 KB Output is correct
22 Correct 148 ms 110360 KB Output is correct
23 Correct 129 ms 110276 KB Output is correct
24 Correct 337 ms 110396 KB Output is correct
25 Correct 92 ms 109636 KB Output is correct
26 Correct 128 ms 110284 KB Output is correct
27 Correct 112 ms 110304 KB Output is correct
28 Correct 113 ms 110316 KB Output is correct
29 Correct 152 ms 110288 KB Output is correct
30 Correct 152 ms 110332 KB Output is correct
31 Correct 145 ms 110360 KB Output is correct
32 Correct 226 ms 110280 KB Output is correct
33 Correct 426 ms 110280 KB Output is correct
34 Correct 1004 ms 110276 KB Output is correct
35 Correct 918 ms 110304 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 629 ms 853700 KB Output is correct
3 Correct 643 ms 860408 KB Output is correct
4 Correct 649 ms 862032 KB Output is correct
5 Correct 704 ms 862060 KB Output is correct
6 Correct 658 ms 860504 KB Output is correct
7 Correct 683 ms 858624 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 130 ms 110288 KB Output is correct
10 Correct 122 ms 110284 KB Output is correct
11 Correct 106 ms 110396 KB Output is correct
12 Correct 104 ms 110372 KB Output is correct
13 Correct 177 ms 110292 KB Output is correct
14 Correct 323 ms 110272 KB Output is correct
15 Correct 122 ms 110316 KB Output is correct
16 Correct 117 ms 110356 KB Output is correct
17 Correct 121 ms 110268 KB Output is correct
18 Correct 140 ms 110296 KB Output is correct
19 Correct 1719 ms 110316 KB Output is correct
20 Correct 1741 ms 110344 KB Output is correct
21 Correct 3 ms 5332 KB Output is correct
22 Correct 111 ms 110376 KB Output is correct
23 Correct 127 ms 110428 KB Output is correct
24 Correct 112 ms 110308 KB Output is correct
25 Correct 107 ms 110304 KB Output is correct
26 Correct 165 ms 110340 KB Output is correct
27 Correct 130 ms 110268 KB Output is correct
28 Correct 136 ms 110368 KB Output is correct
29 Correct 148 ms 110360 KB Output is correct
30 Correct 129 ms 110276 KB Output is correct
31 Correct 337 ms 110396 KB Output is correct
32 Correct 92 ms 109636 KB Output is correct
33 Correct 128 ms 110284 KB Output is correct
34 Correct 112 ms 110304 KB Output is correct
35 Correct 113 ms 110316 KB Output is correct
36 Correct 152 ms 110288 KB Output is correct
37 Correct 152 ms 110332 KB Output is correct
38 Correct 145 ms 110360 KB Output is correct
39 Correct 226 ms 110280 KB Output is correct
40 Correct 426 ms 110280 KB Output is correct
41 Correct 1004 ms 110276 KB Output is correct
42 Correct 918 ms 110304 KB Output is correct
43 Correct 2 ms 3156 KB Output is correct
44 Correct 4 ms 5332 KB Output is correct
45 Correct 844 ms 865208 KB Output is correct
46 Correct 665 ms 860632 KB Output is correct
47 Correct 683 ms 861080 KB Output is correct
48 Correct 708 ms 863228 KB Output is correct
49 Correct 872 ms 865232 KB Output is correct
50 Correct 671 ms 862788 KB Output is correct
51 Correct 630 ms 863176 KB Output is correct
52 Correct 670 ms 860924 KB Output is correct
53 Correct 1178 ms 861664 KB Output is correct
54 Correct 1271 ms 863020 KB Output is correct
55 Correct 1730 ms 861760 KB Output is correct
56 Correct 2443 ms 862424 KB Output is correct
57 Correct 1761 ms 862476 KB Output is correct
58 Correct 1994 ms 862504 KB Output is correct
59 Correct 1890 ms 862672 KB Output is correct
60 Correct 2298 ms 861908 KB Output is correct
61 Correct 2162 ms 861960 KB Output is correct