Submission #793937

#	Time	Username	Problem	Language	Result	Execution time	Memory
793937		mathematik	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	4692 ms	1905452 KiB

dungeons

        #include "dungeons.h"
        #include <bits/stdc++.h>
        #define ll long long
         
        using namespace std;
         
        int binary_index[16][400001][25];//index, +, max excluded
        int binary_add[16][400001][25];
        int binary_max[16][400001][25];
         
        ll min(int a, ll b) {
        	return a < b ? a : b;
        }
         
        int N;
        vector<int> S, P, W, L;
         
        int safe_add(int a, int b) {
        	if (a > INT_MAX - b)
        		return INT_MAX;
        	return a + b;
        }
         
        int safe_sub(int a, int b) {
        	return max(a - b, 0);
        }
         
        void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
        	s.push_back(0);
        	p.push_back(0);
        	w.push_back(n);
        	l.push_back(n);
        	n++;
         
        	N = n;
        	S = s, P = p, W = w, L = l;
         
        	for (int range = 0; range < 16; range++)
        	{
        		ll r = 1 << (range + 9);
         
        		for (int i = 0; i < n; i++)
        		{
        			if (s[i] <= r) {
        				binary_index[range][i][0] = w[i];
        				binary_add[range][i][0] = s[i];
        				binary_max[range][i][0] = INT_MAX;
        			} else {
        				binary_index[range][i][0] = l[i];
        				binary_add[range][i][0] = p[i];
        				binary_max[range][i][0] = s[i];
        			}
        		}
        		
        		for (int i = 1; i < 25; i++)
        		{
        			for (int ind = 0; ind < n; ind++)
        			{
        				int pointer = binary_index[range][ind][i - 1];
        				binary_index[range][ind][i] = binary_index[range][pointer][i - 1];
        				binary_add[range][ind][i] = safe_add(binary_add[range][ind][i - 1], binary_add[range][pointer][i - 1]);
        				binary_max[range][ind][i] = min(binary_max[range][ind][i - 1], safe_sub(binary_max[range][pointer][i - 1], binary_add[range][ind][i - 1]));
        			}
        		}
        	}
        }
         
        long long simulate(int x, int z) {
        	ll t = z;
         
        	while (t < 512 && x != N - 1) {
        		if (t >= S[x]) {
        			t += S[x];
        			x = W[x];
        		} else {
        			t += P[x];
        			x = L[x];
        		}
        	}
         
        	for (int r = 0; r < 16; r++)
        	{
        		for (int s = 24; s >= 0; s--)
        		{
        			while (binary_max[r][x][s] > t && x != N - 1 && binary_add[r][x][s] != INT_MAX) {
        				t += binary_add[r][x][s];
        				x = binary_index[r][x][s];
        			}
        		}
        	}
        	return t;
        }

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