Submission #1088999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088999		StefanSebez	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	305 ms	132664 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=4e5+50,lg=22;
ll inf=1e18;
ll n,s[N],p[N],w[N],l[N],maks;
//ll par[N][lg+1],par1[N][lg+1],sum[N][lg+1],sum1[N][lg+1];
ll par[N/4][lg+1][7],sum[N/4][lg+1][7];
vector<ll>Vals;
//int IND(int x){for(int i=0;i<Vals.size();i++) if(Vals[i]==x) return i;}
void init(int n1, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) {
	n=n1;
	for(int i=0;i<n;i++){s[i]=s1[i],p[i]=p1[i],w[i]=w1[i],l[i]=l1[i];maks=max(maks,s[i]);Vals.pb(s[i]);}
	sort(Vals.begin(),Vals.end());
	int mmm=unique(Vals.begin(),Vals.end())-Vals.begin();
	Vals.resize(mmm);
	//for(auto i:Vals) printf("%lld ",i);printf("\n");
	for(int i=0;i<n;i++){
		/*par[i][0]=w[i];
		par1[i][0]=l[i];
		sum[i][0]=p[i];*/
		for(int j=0;j<=Vals.size();j++){
			ll R=inf;if(j!=Vals.size()) R=Vals[j];
			if(s[i]<R){
				par[i][0][j]=w[i];
				sum[i][0][j]=s[i];
			}
			else{
				par[i][0][j]=l[i];
				sum[i][0][j]=p[i];
			}
		}
	}
	for(int i=0;i<=lg;i++) for(int j=0;j<=5;j++) par[n][i][j]=n;
	for(int j=1;j<=lg;j++){
		for(int i=0;i<n;i++){
			for(int k=0;k<=Vals.size();k++){
				par[i][j][k]=par[par[i][j-1][k]][j-1][k];
				sum[i][j][k]=sum[i][j-1][k]+sum[par[i][j-1][k]][j-1][k];
			}
		}
	}
	//for(int j=1;j<=lg;j++) for(int i=0;i<n;i++){par[i][j]=par[par[i][j-1]][j-1];par1[i][j]=par1[par1[i][j-1]][j-1];sum[i][j]=sum[i][j-1]+sum[par1[i][j-1]][j-1];}
	//for(int i=0;i<=n;i++) for(int j=0;j<=5;j++) printf("%i %i: %lld %lld %lld\n",i,j,par[i][j],par1[i][j],sum[i][j]);
	return;
}

long long simulate(int x, int z) {
	ll Z=z;
	/*while(x<n && Z<maks){
		if(Z>=s[x]){
			Z+=s[x];
			x=w[x];
		}
		else{
			Z+=p[x];
			x=l[x];
		}
		//printf("*%i %lld\n",x,Z);
	}*/
	/*for(int i=lg;i>=0;i--){
		if(Z+sum[x][i]<s[0] && par1[x][i]<n){
			Z+=sum[x][i];
			x=par1[x][i];
		}
	}
	if(Z<s[x]){
		Z+=p[x];
		x=l[x];
	}*/
	/*for(int i=lg;i>=0;i--){
		if(par[x][i]<n){
			ll val=(ll)1<<i;
			Z+=sum[x][i];
			x=par[x][i];
		}
	}
	if(x<n){
		Z+=s[x];
		x=w[x];
	}*/
	for(int k=0;k<=Vals.size();k++){
		ll R=inf;if(k!=Vals.size()) R=Vals[k];
		//printf("|%i %lld\n",k,R);
		for(int i=lg;i>=0;i--){
			//printf("%i %i %i: %lld %lld %lld %lld\n",x,i,k,par[x][i][k],sum[x][i][k],Z+sum[x][i][k],R);
			if(par[x][i][k]<n && Z+sum[x][i][k]<R){
				Z+=sum[x][i][k];
				x=par[x][i][k];
				//printf("da\n");
			}
		}
		//printf("*%i %lld\n",x,Z);
		if(x<n && Z<R){
			if(Z>=s[x]){
				Z+=s[x];
				x=w[x];
			}
			else{
				Z+=p[x];
				x=l[x];
			}
		}
		//printf("*%i %lld\n",x,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:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int j=0;j<=Vals.size();j++){
      |               ~^~~~~~~~~~~~~
dungeons.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    ll R=inf;if(j!=Vals.size()) R=Vals[j];
      |                ~^~~~~~~~~~~~~
dungeons.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int k=0;k<=Vals.size();k++){
      |                ~^~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int k=0;k<=Vals.size();k++){
      |              ~^~~~~~~~~~~~~
dungeons.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   ll R=inf;if(k!=Vals.size()) R=Vals[k];
      |               ~^~~~~~~~~~~~~

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