Submission #1179718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179718		Gr1sen	Dungeons Game (IOI21_dungeons)	C++20	37 / 100	7056 ms	1353352 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>

using namespace std;

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pi pair<ll, ll>
#define vp vector<pi>
#define vvp vector<vp>

ll oo = (ll)1 << 60;

struct node {
	ll max = -1; // max or min
	ll min = -1;
	ll to = -1;
	ll gain = -1;
	void print() {
		cerr << "node : {max : " << max << ", min : " << min << ", to : " << to << ", gain : " << gain << "}\n";
	}
};

int n;
vi S, P, W, L;
vector<map<ll, node>> B1, B;

void print(vi &L1) {
	cerr << "{";
	for (auto i : L1) {
		cerr << i << ", ";
	}
	cerr << "}\n";
}

void print(vl &L1) {
	cerr << "{";
	for (auto i : L1) {
		cerr << i << ", ";
	}
	cerr << "}\n";
}

void print(vector<vector<node>> &L1) {
	cerr << "{\n";
	for (auto i : L1) {
		cerr << "{\n";
		for (auto j : i) {
			j.print();
		}
		cerr << "},\n";
	}
	cerr << "}\n";
}

void print(vector<map<ll, node>> &L1) {
	cerr << "{\n";
	for (auto i : L1) {
		cerr << "{\n";
		for (auto j : i) {
			cerr << j.first << " : ";
			j.second.print();
		}
		cerr << "},\n";
	}
	cerr << "}\n";
}

void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	n = N;
	S = s;
	P = p;
	W = w;
	L = l;
	B1 = vector<map<ll, node>>(n);
	B = vector<map<ll, node>>(n);
	//cerr << "oo : " << oo << endl;
	
	for (int i = 0; i < n; i++) {
		B1[i] = {{0, {S[i], 0, L[i], P[i]}}, {S[i], {oo, S[i], W[i], S[i]}}};
	}

	//cerr << "B1 : ";
	//print(B1);

	for (int i = 0; i < log2(n)+2; i++) {
		for (int j = 0; j < n; j++) {
			B[j] = {};
			for (auto i : B1[j]) {
				node a = i.second;
				if (a.to == n) {
					B[j][a.min] = a;
					continue;
				}
				for (auto i : B1[a.to]) {
					node b = i.second;
					if (a.min + a.gain >= b.max) continue;
					if (a.max + a.gain <= b.min) continue;
					node c = {min(oo, min(a.max, b.max - a.gain)), max((ll)0, max(a.min, b.min - a.gain)), b.to, a.gain + b.gain};
					if (B[j].find(c.min) != B[j].end()) {
						//cerr << "ERROR B[" << j << "][" << c.min << "] already exist\n";
						//cerr << "B[" << j << "][" << c.min << "] : ";
						//B[j][c.min].print();
						//cerr << "c : ";
						//c.print();
					}
					B[j][c.min] = c;
				}
			}
		}
		B1 = B;
	}

	/*
	print(B);
	//*/
	return;
}

ll oink(ll x, ll z) {
	if (x == n) return z;
	auto a = B[x].upper_bound(z);
	a--;
	return oink((*a).second.to, z + (*a).second.gain);
}

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

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