Submission #602610

#	Time	Username	Problem	Language	Result	Execution time	Memory
602610		rrrr10000	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	1280 ms	2097156 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef tuple<ll,ll,ll> PP;
typedef vector<PP> vpp;
typedef vector<vpp> vvpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;

ll n;
vi s,p,w,l;
vector<vvp> table;
vvi nex;
vi al;
P f(P a,P b){
	return P(b.fi,a.se+b.se);
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_){
	n=n_+1;
	for(ll x:s_)s.pb(x);
	for(ll x:p_)p.pb(x);
	for(ll x:w_)w.pb(x);
	for(ll x:l_)l.pb(x);
	s.pb(0);p.pb(0);w.pb(n-1);l.pb(n-1);
	al=s;dupli(al);
	table=vector<vvp>(al.size(),vvp(20,vp(n)));
	rep(t,al.size()){
		rep(i,n){
			if(al[t]>=s[i])table[t][0][i]=P(w[i],s[i]);
			else table[t][0][i]=P(l[i],p[i]);
		}
		rep(i,19)rep(j,n)table[t][i+1][j]=f(table[t][i][j],table[t][i][table[t][i][j].fi]);
	}
	return;
}

long long simulate(int x_, int z_) {
	ll i=x_,cur=z_;
	/*
	while(i<n-1){
		if(cur>=s[i]){
			cur+=s[i];
			i=w[i];
		}
		else{
			cur+=p[i];
			i=l[i];
		}
	}
	*/
	while(i<n-1){
		/*
		if(cur<s[i]){
			cur+=p[i];i=l[i];
		}
		else{
			PP tmp(i,0,0);
			for(ll j=19;j>=0;j--){
				auto ntmp=f(tmp,table[j][get<0>(tmp)]);
				if(get<1>(ntmp)<=cur){
					tmp=ntmp;
				}
			}
			i=get<0>(tmp);cur+=get<2>(tmp);
		}
		*/
		ll t=lb(al,cur+1)-1,mx=inf;
		if(t!=al.size()-1)mx=al[t+1];
		P tmp(i,cur);
		for(ll j=19;j>=0;j--){
			auto ntmp=f(tmp,table[t][j][tmp.fi]);
			if(ntmp.se<mx)tmp=ntmp;
		}
		tmp=f(tmp,table[t][0][tmp.fi]);
		i=tmp.fi;cur=tmp.se;
	}
	return cur;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:82:7: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   if(t!=al.size()-1)mx=al[t+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