Submission #443532

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
443532	2021-07-10 17:19:28	JvThunder	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2518 ms	915516 KiB

dungeons

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;
//constants
int base = 5; // base here means doing in 2^base
        // use a higher base instead of 2 for the phase ranges to make the memory efficient
        // note: using a smaller base decreases runtime but increases memory
        
const int nop = 5; // no of phase
const int noa = 19; // no of ancestor for binlift
const int sz = 400005; // max size of N
int INF = 1e9+7;
ll add[sz] = {0}; // add[i] = str increase if start at i & win all
pair<int,pair<int,ll>> jump[nop][noa][sz]; // store: jump dest, min(str_opp - str_gained), str_inc
                     // jump[a][b][i] is game simulation starting from index i &
                     // jump 2^b steps ahead assuming only win against everything <=8^a
int N;
vector<int> S,P,W,L; 
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
  S = s; P = p; W = w; L = l; N = n;
  // add dummy node for index n
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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