제출 #453629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
453629		flappybird	던전 (IOI21_dungeons)	C++17	11 / 100	7063 ms	238032 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

#define MAXS 40 //MAX sparse table
#define MAXI 9 //MAX interval
#define INF 1010101010
#define MAX 404040
#define B 3

vector<pll> win, lose; //next
int nxt[9][40][404040], limit[9][40][404040];
int delta[9][40][404040];
ll dp[404040];
int N;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n;
	ll i;
	win.resize(N + 1);
	lose.resize(N + 1);
	for (i = 0; i < N; i++) {
		win[i] = { w[i], s[i] };
		lose[i] = { l[i], p[i] };
	}
	ll k;
	for (k = 0; k < MAXI; k++) {
		ll low, high;
		low = 1 << (B * k);
		high = 1 << (B * (k + 1));
		for (i = 0; i < N; i++) {
			if (s[i] < low) {
				nxt[k][0][i] = win[i].first;
				delta[k][0][i] = win[i].second;
				limit[k][0][i] = INF;
			}
			else if (s[i] >= high) {
				nxt[k][0][i] = lose[i].first;
				delta[k][0][i] = lose[i].second;
				limit[k][0][i] = s[i];
			}
			else {
				nxt[k][0][i] = lose[i].first;
				delta[k][0][i] = lose[i].second;
				limit[k][0][i] = s[i];
			}
		}
		nxt[k][0][N] = N;
		delta[k][0][N] = 0;
		limit[k][0][N] = INF;
		ll j;
		for (j = 1; j < k + 1; j++) {
			for (i = 0; i <= N; i++) {
				ll v = nxt[k][j - 1][i];
				nxt[k][j][i] = nxt[k][j - 1][v];
				delta[k][j][i] = delta[k][j - 1][i] + delta[k][j - 1][v];
				limit[k][j][i] = (int)max(0LL, min((ll)limit[k][j - 1][v] - delta[k][j - 1][i], (ll)limit[k][j - 1][i]));
			}
		}
	}
	return;
}

ll get(ll x) {
	if (dp[x]) return dp[x];
	if (x == N) return 0;
	return dp[x] = (win[x].second + get(win[x].first));
}

long long f(ll x, ll z) {
	ll i;
	for (i = 0; i < MAXI; i++) {
		ll low, high;
		high = 1 << (B * (i + 1));
		if (i == MAXI - 1) return z + get(x);
		if (high <= z) continue;
		ll k;
		ll c = 1;
		while (c) {
			c = 0;
			if (high <= z) break;
			for (k = 3 * i + 2; k >= 0; k--) {
				if (limit[i][k][x] > z) {
					c = 1;
					z += delta[i][k][x];
					x = nxt[i][k][x];
				}
				if (high <= z) break;
				if (x == N) return z;
			}
			if (high <= z) break;
			if (c == 0) {
				if (z >= win[x].second) z += win[x].second, x = win[x].first;
				else z += lose[x].second, x = lose[x].first;
				if (x == N) return z;
				if (high <= z) break;
				c = 1;
			}
			if (x == N) return z;
			if (high <= z) break;
		}
	}
	return z;
}

long long simulate(int x, int z) {
	return f(x, z);
}

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'long long int f(ll, ll)':
dungeons.cpp:79:6: warning: unused variable 'low' [-Wunused-variable]
   79 |   ll low, high;
      |      ^~~

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