Submission #1130477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130477		patgra	Dungeons Game (IOI21_dungeons)	C++20	Compilation error	0 ms	0 KiB

dungeons

#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) + 1;
constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
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) {
	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;
		}
		while (myJp.toAdd >= sectionStart[section + 1] && 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;
}
#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) + 1;
constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
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) {
	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;
		}
		while (myJp.toAdd >= sectionStart[section + 1] && 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;
}

Compilation message (stderr)

dungeons.cpp:132:16: error: redefinition of 'constexpr const bool dbg'
  132 | constexpr bool dbg = 0;
      |                ^~~
dungeons.cpp:11:16: note: 'constexpr const bool dbg' previously defined here
   11 | constexpr bool dbg = 0;
      |                ^~~
dungeons.cpp:139:15: error: redefinition of 'constexpr const int maxn'
  139 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |               ^~~~
dungeons.cpp:18:15: note: 'constexpr const int maxn' previously defined here
   18 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |               ^~~~
dungeons.cpp:139:42: error: redefinition of 'constexpr const int jpBase'
  139 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |                                          ^~~~~~
dungeons.cpp:18:42: note: 'constexpr const int jpBase' previously defined here
   18 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |                                          ^~~~~~
dungeons.cpp:139:54: error: redefinition of 'constexpr const int maxLog'
  139 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |                                                      ^~~~~~
dungeons.cpp:18:54: note: 'constexpr const int maxLog' previously defined here
   18 | constexpr int maxn = dbg ? 10 : 4e5 + 7, jpBase = 3, maxLog = log(maxn) / log(jpBase) + 1;
      |                                                      ^~~~~~
dungeons.cpp:140:15: error: redefinition of 'constexpr const int maxPower'
  140 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |               ^~~~~~~~
dungeons.cpp:19:15: note: 'constexpr const int maxPower' previously defined here
   19 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |               ^~~~~~~~
dungeons.cpp:140:47: error: redefinition of 'constexpr const int sectionsBase'
  140 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |                                               ^~~~~~~~~~~~
dungeons.cpp:19:47: note: 'constexpr const int sectionsBase' previously defined here
   19 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |                                               ^~~~~~~~~~~~
dungeons.cpp:140:65: error: redefinition of 'constexpr const int sections'
  140 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |                                                                 ^~~~~~~~
dungeons.cpp:19:65: note: 'constexpr const int sections' previously defined here
   19 | constexpr int maxPower = dbg ? 100 : 7e7 + 7, sectionsBase = 3, sections = log(maxPower) / log(sectionsBase) + 2;
      |                                                                 ^~~~~~~~
dungeons.cpp:141:14: error: redefinition of 'constexpr const long long int inf'
  141 | constexpr ll inf = 1e18;
      |              ^~~
dungeons.cpp:20:14: note: 'constexpr const long long int inf' previously defined here
   20 | constexpr ll inf = 1e18;
      |              ^~~
dungeons.cpp:142:5: error: redefinition of 'int gn'
  142 | int gn;
      |     ^~
dungeons.cpp:21:5: note: 'int gn' previously declared here
   21 | int gn;
      |     ^~
dungeons.cpp:143:5: error: redefinition of 'int monsterPower [400007]'
  143 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |     ^~~~~~~~~~~~
dungeons.cpp:22:5: note: 'int monsterPower [400007]' previously declared here
   22 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |     ^~~~~~~~~~~~
dungeons.cpp:143:25: error: redefinition of 'int consolationPrize [400007]'
  143 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                         ^~~~~~~~~~~~~~~~
dungeons.cpp:22:25: note: 'int consolationPrize [400007]' previously declared here
   22 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                         ^~~~~~~~~~~~~~~~
dungeons.cpp:143:49: error: redefinition of 'int winPointer [400007]'
  143 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                                                 ^~~~~~~~~~
dungeons.cpp:22:49: note: 'int winPointer [400007]' previously declared here
   22 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                                                 ^~~~~~~~~~
dungeons.cpp:143:67: error: redefinition of 'int losePointer [400007]'
  143 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                                                                   ^~~~~~~~~~~
dungeons.cpp:22:67: note: 'int losePointer [400007]' previously declared here
   22 | int monsterPower[maxn], consolationPrize[maxn], winPointer[maxn], losePointer[maxn];
      |                                                                   ^~~~~~~~~~~
dungeons.cpp:144:4: error: redefinition of 'long long int sectionStart [18]'
  144 | ll sectionStart[sections];
      |    ^~~~~~~~~~~~
dungeons.cpp:23:4: note: 'long long int sectionStart [18]' previously declared here
   23 | ll sectionStart[sections];
      |    ^~~~~~~~~~~~
dungeons.cpp:150:8: error: redefinition of 'struct jpStruct'
  150 | struct jpStruct {
      |        ^~~~~~~~
dungeons.cpp:29:8: note: previous definition of 'struct jpStruct'
   29 | struct jpStruct {
      |        ^~~~~~~~
dungeons.cpp:154:3: error: conflicting declaration 'int jp [400007][18][12]'
  154 | } jp[maxn][sections][maxLog];
      |   ^~
dungeons.cpp:33:3: note: previous declaration as 'jpStruct jp [400007][18][12]'
   33 | } jp[maxn][sections][maxLog];
      |   ^~
dungeons.cpp:156:10: error: redefinition of 'jpStruct merge(jpStruct, jpStruct)'
  156 | jpStruct merge(jpStruct a, jpStruct b) {
      |          ^~~~~
dungeons.cpp:35:10: note: 'jpStruct merge(jpStruct, jpStruct)' previously defined here
   35 | jpStruct merge(jpStruct a, jpStruct b) {
      |          ^~~~~
dungeons.cpp:167:6: error: redefinition of 'void initJPsection(int)'
  167 | void initJPsection(int section) {
      |      ^~~~~~~~~~~~~
dungeons.cpp:46:6: note: 'void initJPsection(int)' previously defined here
   46 | void initJPsection(int section) {
      |      ^~~~~~~~~~~~~
dungeons.cpp:187:6: error: redefinition of 'void initJP()'
  187 | void initJP() {
      |      ^~~~~~
dungeons.cpp:66:6: note: 'void initJP()' previously defined here
   66 | void initJP() {
      |      ^~~~~~
dungeons.cpp:201:6: error: redefinition of 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)'
  201 | void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
      |      ^~~~
dungeons.cpp:80:6: note: 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
   80 | void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
      |      ^~~~
dungeons.cpp:217:11: error: redefinition of 'long long int simulate(int, int)'
  217 | long long simulate(int x, int z) {
      |           ^~~~~~~~
dungeons.cpp:96:11: note: 'long long int simulate(int, int)' previously defined here
   96 | long long simulate(int x, int z) {
      |           ^~~~~~~~