Submission #464219

#	Time	Username	Problem	Language	Result	Execution time	Memory
464219		flappybird	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	7094 ms	1690412 KiB

dungeons

//주석 추가
#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 25 //MAX interval
#define MAXSI 351
#define INF 10101010
#define MAX 404040
#define B 1
#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

vector<pair<int, int>> win, lose; //next
int nxt[MAX][MAXSI], limit[MAX][MAXSI], delta[MAX][MAXSI];
//nxt[i][j][k]: i번 정점에서 힘이[1<<j, 1<<(j+1)-1]범위일때 2^k번의 연속된 패배후 도달하는 정점
//메모리 초과로 인해 nxt[i][k+j*(j+1)/2]에 압축하여 저장해 메모리 사용량을 반으로 줄임
//delta, limit은 i에서 nxt로 갈때 계속 패배하면서 갈 때 증가하는 힘과 계속 패배하며 갈 수 있는 힘의 조건
ll dp[MAX];
int f[30][30];
//[k+j*(j+1)/2]를 저장
int N;

//x에서 시작했을때 승리만 하면서 N에 도착했을때 증가한 힘의 양(dp배열에 저장)
ll get(int x) {
	if (x == N) return 0;
	if (dp[x]) return dp[x];
	return dp[x] = get(win[x].first) + win[x].second;
}

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n;
	int i, j;
	for (i = 0; i <= 25; i++) {
		for (j = 0; j <= i; j++) f[i][j] = j + (i * (i + 1) / 2);
	}
  //win, lose에는 w, s, l, p를 저장
	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] };
	}
	int k;
  //세 개의 배열을 만드는 과정
  //힘이[2^k, 2^(k+1))-1] 사이일때
	for (k = 0; k < MAXI; k++) {
		int low, high;
		low = 1 << k;
		high = 1 << (k + 1);
		for (i = 0; i < N; i++) {
			if (s[i] < low) {
				nxt[i][f[k][0]] = win[i].first;
				delta[i][f[k][0]] = win[i].second;
				limit[i][f[k][0]] = INF;
			}
			else if (s[i] >= high) {
				nxt[i][f[k][0]] = lose[i].first;
				delta[i][f[k][0]] = lose[i].second;
				limit[i][f[k][0]] = s[i];
			}
			else {
				nxt[i][f[k][0]] = lose[i].first;
				delta[i][f[k][0]] = lose[i].second;
				limit[i][f[k][0]] = s[i];
			}
		}
		nxt[N][f[k][0]] = N;
		delta[N][f[k][0]] = 0;
		limit[N][f[k][0]] = INF;
		int j;
      //스파스 테이블을 만들어 줌
		for (j = 1; j <= k; ++j) {
			for (i = 0; i <= N; ++i) {
				int v = nxt[i][f[k][j - 1]];
				nxt[i][f[k][j]] = nxt[v][f[k][j - 1]];
              //힘이 일정 이상 커지면 계속 승리하므로, int에 저장하기 위해 delta 배열의 상한을 지정함
				delta[i][f[k][j]] = min(50000000, delta[i][f[k][j - 1]] + delta[v][f[k][j - 1]]);
				limit[i][f[k][j]] = max(0, min(limit[v][f[k][j - 1]] - delta[i][f[k][j - 1]], limit[i][f[k][j - 1]]));
			}
		}
	}
	for (i = 0; i < N; i++) get(i);
	return;
}

long long simulate(int x, int Z) {
	ll z = Z;
	ll i;
  //힘이 각 구간([2^i, 2^(i+1)-1])에 있는 상태를 유지할 때까지 계속 x를 이동시키고, 구간을 벗어나면 다음 구간에서 시뮬레이션함
	for (i = 0; i < MAXI; i++) {
		ll high;
		high = 1 << (i + 1);
		if (i == MAXI - 1) break;
		if (high <= z) continue;
		int k;
		bool c = 0;
		for (k = i; k >= 0; k--) {
			while (limit[x][f[i][k]] > z) {
				if (delta[x][f[i][k]] > 20000000) {
                  //init의 min연산으로 인해 delta에 저장된 값이 유효하지 않을 수 있음
					c = 1;
					break;
				}
				z += delta[x][f[i][k]];
				x = nxt[x][f[i][k]];
				if (high <= z) break;
				if (x == N) return z;
			}
			if (c) break;
			if (high <= z) break;
			if (x == N) return z;
		}
		if (x == N) return z;
		if (c) {
          //위에서 delta가 2천만 이상인 경우 -> 값이 유효하지 않을 수 있음
          //k를 더 감소시키면서 유효한 값을 찾아주고, 그 k부터 처리함
			for (; k >= 0; k--) {
				if (limit[x][f[i][k]] > z) {
					while (delta[x][f[i][k]] <= 20000000) {
						z += delta[x][f[i][k]];
						x = nxt[x][f[i][k]];
						if (z > 1000000) return z + dp[x];
						if (high <= z) break;
						if (x == N) return z;
					}
					if (high <= z) break;
					if (x == N) return z;
				}
			}
			if (z > 1000000) return z + dp[x];
			continue;
		}
		if (high <= z) continue;
		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) break;
	}
  //가장 큰 구간에서도 벗어난 경우는 항상 승리함
	return z + dp[x];
}

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