Submission #1072064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072064		noyancanturk	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	249 ms	307808 KiB

dungeons

#include "dungeons.h"

#include<bits/stdc++.h>
using namespace std;

using lint=long long;

const int lim=5e4+100,llim=25;

int n;
int jump[10][lim][llim];
lint lift[10][lim][llim];

vector<int>vals;

void init(int N,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
	n=N;
	set<int>st;
	st.insert(0);
	st.insert(LLONG_MAX);
	for(int i=0;i<n;i++){
		st.insert(s[i]);
	}
	vals=vector<int>(st.begin(),st.end());
	for(int i=0;i<vals.size();i++){
		for(int j=0;j<n;j++){
			if(s[j]<=vals[i]){
				jump[i][j][0]=w[j];
				lift[i][j][0]=s[j];
			}else{
				jump[i][j][0]=l[j];
				lift[i][j][0]=p[j];
			}
		}
		jump[i][n][0]=n;
		lift[i][n][0]=0;
		for(int k=1;k<llim;k++){
			for(int j=0;j<=n;j++){
				jump[i][j][k]=jump[i][jump[i][j][k-1]][k-1];
				lift[i][j][k]=lift[i][j][k-1]+lift[i][jump[i][j][k-1]][k-1];
			}
		}
	}
}

long long simulate(int x, int Z) {
	lint z=Z;
	int ind=0;
	while(ind+1<vals.size()&&vals[ind+1]<=z)ind++;
	while(1){
		if(ind+1<vals.size()&&vals[ind+1]<=z){
			ind++;
			continue;
		}
		for(int i=llim-1;0<=i;i--){
			if(ind+1==vals.size()||z+lift[ind][x][i]<vals[ind+1]){
				z+=lift[ind][x][i];
				x=jump[ind][x][i];
			}
		}
		z+=lift[ind][x][0];
		x=jump[ind][x][0];
		if(x==n)return z;
		ind++;
	}
	return -1;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:20:12: warning: overflow in conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} changes value from '9223372036854775807' to '-1' [-Woverflow]
   20 |  st.insert(LLONG_MAX);
      |            ^~~~~~~~~
dungeons.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<vals.size();i++){
      |              ~^~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  while(ind+1<vals.size()&&vals[ind+1]<=z)ind++;
      |        ~~~~~^~~~~~~~~~~~
dungeons.cpp:51:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   if(ind+1<vals.size()&&vals[ind+1]<=z){
      |      ~~~~~^~~~~~~~~~~~
dungeons.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    if(ind+1==vals.size()||z+lift[ind][x][i]<vals[ind+1]){
      |       ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11