Submission #744294

#	Time	Username	Problem	Language	Result	Execution time	Memory
744294		myrcella	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	500 ms	765180 KiB

dungeons

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

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "dungeons.h"

const int maxn = 4e5+10;

int nn;
ll ss[maxn],pp[maxn],ww[maxn],lr[maxn];
vector <int> val;
ll ans[maxn];
int st[5][16][maxn];
ll gain[5][16][maxn];
int circleindex[5][maxn];
vector <int> node[5];
ll circlesum[5][maxn];
int circlesz[5];
int nxt[5][maxn];
int vis[maxn];
stack <int> stk;

void dfs(int id,int u) {
	stk.push(u);
	vis[u] = 1;
	if (vis[nxt[id][u]]==1) {
		while (1) {
			int cur = stk.top();
			node[id].pb(cur);
			stk.pop();
			if (cur==nxt[id][u]) break;
		}
		node[id].pb(-1);
		reverse(ALL(node[id]));
		for (auto it:node[id]) stk.push(it);
	}
	else if (vis[nxt[id][u]]==0) dfs(id,nxt[id][u]);
	stk.pop();
	vis[u]=2;
}

void gen(int id,int x) {
	rep(i,0,nn) nxt[id][i] = x>=ss[i]?ww[i]:lr[i];
	memset(vis,0,sizeof(vis));
	
	rep(i,0,nn) if (vis[i]==0) {
		while (!stk.empty()) stk.pop();
		dfs(id,i);
	}
	circlesz[id] = SZ(node[id])-1;
	int sz = circlesz[id];
	rep(i,1,2*sz+1) {
		if (i<=sz) {
			circlesum[id][i] = circlesum[id][i-1] + (x>=ss[node[id][i]]?ss[node[id][i]]:pp[node[id][i]]);
			circleindex[id][node[id][i]] = i;
		}
		else circlesum[id][i] = circlesum[id][i-1] + (x>=ss[node[id][i-sz]]?ss[node[id][i-sz]]:pp[node[id][i-sz]]);
	}
	rep(i,0,nn) if (circleindex[id][i]==-1) st[id][0][i] = nxt[id][i], gain[id][0][i] = x>=ss[i]?ss[i]:pp[i];
	rep(i,1,16) rep(j,0,nn) {
		if (circleindex[id][j]!=-1) continue;
		if (st[id][i-1][j]==-1) continue;
		st[id][i][j] = st[id][i-1][st[id][i-1][j]];
		gain[id][i][j] = gain[id][i-1][j] + gain[id][i-1][st[id][i-1][j]];
	}
}

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	memset(circleindex,-1,sizeof(circleindex));
	memset(st,-1,sizeof(st));
	memset(gain,inf,sizeof(gain));
	nn = N;
	rep(i,0,nn) ss[i] = S[i], pp[i] = P[i], ww[i] = W[i], lr[i] = L[i],val.pb(ss[i]);
	sort(ALL(val));
	val.erase(unique(ALL(val)),val.end());reverse(ALL(val));
	ans[nn] = 0;
	for (int i=nn-1;i>=0;i--) ans[i] = ss[i] + ans[ww[i]];
	int hi = 0;
	for (int i = SZ(val)-1;i>=0;i--) gen(i,hi),hi = val[i];
	return;
}

long long simulate(int x, int z) {
	vector <int> valcur = val;
	
	ll ret = z;
	while (!valcur.empty()) {
		while (!valcur.empty() and ret >= valcur.back()) valcur.pop_back();
		if (valcur.empty()) break;
		int goal = valcur.back();
		int id = SZ(valcur)-1;
		for (int i=15;i>=0;i--) if (ret + gain[id][i][x] < goal) {
			ret += gain[id][i][x];
			x = st[id][i][x];
		}
		//check whether next step alrd reach goal
		if (x==nn) return ret;
		ll rett = ret;
		if (ret >= ss[x]) rett = ret + ss[x];
		else rett = ret + pp[x];
		if (rett>=goal) {
			x = ret>=ss[x]? ww[x]:lr[x];
			ret = rett;
		}
		else { //circle
			int sz = circlesz[id];
			ret += (goal-ret)/circlesum[id][sz]*circlesum[id][sz];
			int lo = circleindex[id][x], hi = sz*2;
			int index = lo-1;
			while (lo<hi) {
				int mid=lo+hi>>1;
				if (circlesum[id][mid] - circlesum[id][index] + ret >= goal) hi = mid;
				else lo = mid+1;
			}
			if (lo<=sz) x = node[id][lo];
			else x = node[id][lo-sz];
			x = ret>=ss[x]? ww[x]:lr[x];
			ret += circlesum[id][lo] - circlesum[id][index];
			
		}
		valcur.pop_back();
//		debug(ret);debug(x);
	}
	ret += ans[x];
	return ret;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:130:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |     int mid=lo+hi>>1;
      |             ~~^~~

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