Submission #745307

#	Time	Username	Problem	Language	Result	Execution time	Memory
745307		arthur_nascimento	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2443 ms	865232 KiB

dungeons

#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 (stderr)

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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11