| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1130466 | patgra | 던전 (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dungeons.h"
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)
#define ll long long
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
using namespace std;
constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 3;
constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 3;
constexpr ll inf = 1e18;
int gn;
int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
ll sectionStart[sections];
/*
int jpPointer[maxn][sections][maxLog];
ll jpToAdd[maxn][sections][maxLog];
ll jpStartNeededToWin[maxn][sections][maxLog];
*/
struct jpStruct {
int pointer;
ll toAdd;
ll startNeededToWin;
} jp[maxn][sections][maxLog];
jpStruct merge(jpStruct a, jpStruct b) {
// DC << "\t\t Merge ( { " << a.pointer << " " << a.toAdd << " " << a.startNeededToWin << " } { " << b.pointer << " " << b.toAdd << " " << b.startNeededToWin << " } )" << eol;
if (b.startNeededToWin == inf) b.startNeededToWin = a.startNeededToWin;
else if (a.startNeededToWin == inf) b.startNeededToWin -= a.toAdd;
else b.startNeededToWin = min(a.startNeededToWin, b.startNeededToWin - a.toAdd);
b.toAdd += a.toAdd;
if (b.startNeededToWin < 0) b.startNeededToWin = -1;
// DC << "\t\t -> { " << b.pointer << " " << b.toAdd << " " << b.startNeededToWin << " } " << eol;
return b;
}
void initJPsection(int section) {
if (section == 0) sectionStart[section] = 1;
else sectionStart[section] = sectionStart[section - 1] * sectionsBase;
rep(i, 0, gn + 1) {
if (sectionStart[section] >= monsterPower[i]) {
jp[i][section][0].pointer = winPointer[i];
jp[i][section][0].toAdd = monsterPower[i];
jp[i][section][0].startNeededToWin = inf;
}
else {
jp[i][section][0].pointer = losePointer[i];
jp[i][section][0].toAdd = consolationPrize[i];
jp[i][section][0].startNeededToWin = monsterPower[i];
}
}
rep(k, 1, maxLog) rep(i, 0, gn + 1) {
jp[i][section][k] = jp[i][section][k - 1];
rep(j, 1, jpBase) jp[i][section][k] = merge(jp[i][section][k], jp[jp[i][section][k].pointer][section][k - 1]);
}
}
void initJP() {
rep(i, 0, sections) initJPsection(i);
DEBUG {
DC << "Jump pointers: " << eol;
rep(section, 0, sections) {
DC << " Section: " << section << " range [" << sectionStart[section] << ", " << sectionsBase * sectionStart[section] << ")" << eol;
rep(i, 0, gn + 1) {
DC << " Jump pointers from " << i << eol;
rep(k, 0, maxLog) DC << " " << jpBase << " ^ " << k << " times -> { " << jp[i][section][k].pointer << " " << jp[i][section][k].toAdd << " " << jp[i][section][k].startNeededToWin << " }" << eol;
}
}
}
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
cerr << sections << ' ' << maxLog << eol;
DEBUG {
DC << "_________________________________________________________" << eol << eol;
DC << "maxn = " << maxn << eol;
DC << "maxn log (base " << jpBase << ") = " << maxLog << eol;
DC << "max power = " << maxPower << eol;
DC << "sections = max power log (base " << sectionsBase << ") = " << sections << eol;
DC << "_________________________________________________________" << eol << eol;
}
gn = n;
rep(i, 0, gn) monsterPower[i] = s[i], consolationPrize[i] = p[i], winPointer[i] = w[i], losePointer[i] = l[i];
winPointer[gn] = losePointer[gn] = gn;
initJP();
DC << "_________________________________________________________" << eol << eol;
}
long long simulate(int x, int z) {
DC << "Query " << x << ' ' << z << eol;
jpStruct myJp = {x, z, inf};
int section = 0, lastSection = -1, lastSection2 = -1;
while (myJp.pointer != gn) {
while (section < sections && myJp.toAdd >= sectionStart[section + 1]) section++;
DC << " Going into section " << section << eol;
if (lastSection2 == section) {
DC << " :(" << eol;
return -1;
}
lastSection2 = lastSection;
lastSection = section;
repD(k, maxLog - 1, -1) rep(i, 1, jpBase) if ((jp[myJp.pointer][section][k].startNeededToWin == inf) || (jp[myJp.pointer][section][k].startNeededToWin > myJp.toAdd)) {
DC << " Jumping " << jpBase << " ^ " << k << " times\t\t";
myJp = merge(myJp, jp[myJp.pointer][section][k]);
DC << "New myJp: { " << myJp.pointer << " " << myJp.toAdd << " " << myJp.startNeededToWin << " }" << eol;
}
if (jp[myJp.pointer][section][0].startNeededToWin <= myJp.toAdd) {
DC << " Unaccounted win\t\t";
myJp = merge(myJp, jp[myJp.pointer][sections - 1][0]);
DC << "New myJp: { " << myJp.pointer << " " << myJp.toAdd << " " << myJp.startNeededToWin << " }" << eol;
}
}
return myJp.toAdd;
}