oj.uz

Submission #684086

# Submission time Handle Problem Language Result Execution time Memory
684086 2023-01-20T10:40:06 Z Asymmetry Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 1939940 KB 
#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

#ifdef LOCAL
const int Z = 4;
#else
const int Z = 20;
#endif

const int INF = 1e9;
int n;
vector<int> pot, s, p, w, l;
vector<vector<vector<int>>> jmp, add, lim;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	w.emplace_back(n);
	l.emplace_back(n);
	s.emplace_back(0);
	p.emplace_back(0);
	debug(n, s, p, w, l);
	pot = vector (Z, 1);
	REP (i, Z - 1)
		pot[i + 1] = pot[i] << 1;
	jmp = add = lim = vector(Z, vector(Z, vector(n + 1, 0)));
	REP (k, Z) {
		REP (i, n) {
			if (s[i] <= pot[k]) {
				jmp[k][0][i] = w[i];
				add[k][0][i] = s[i];
				lim[k][0][i] = INF;
			}
			else {
				jmp[k][0][i] = l[i];
				add[k][0][i] = p[i];
				lim[k][0][i] = s[i] - 1;
			}
		}
		jmp[k][0][n] = n;
		add[k][0][n] = 0;
		lim[k][0][n] = -1;
		REP (j, Z - 1) {
			REP (i, n + 1) {
				jmp[k][j + 1][i] = jmp[k][j][jmp[k][j][i]];
				add[k][j + 1][i] = add[k][j][i] + add[k][j][jmp[k][j][i]];
				lim[k][j + 1][i] = min(lim[k][j][i], lim[k][j][jmp[k][j][i]] - add[k][j][i]);
			}
		}
	}
	REP (k, Z)
		REP (j, Z)
			debug(k, j, jmp[k][j], add[k][j], lim[k][j]);
}

LL simulate(int x, int z) {
	int pos = x, tre = 0;
	LL mass = z;
	while (pos != n) {
		while (tre + 1 < Z && pot[tre + 1] <= mass)
			++tre;
		debug(tre, mass, pos);
		for (int i = Z - 1; i >= 0; --i) {
			if (lim[tre][i][pos] >= mass) {
				debug("GO", tre, i, pos, mass, lim[tre][i][pos]);
				mass += add[tre][i][pos];
				pos = jmp[tre][i][pos];
				debug("NEW", tre, i, pos, mass);
			}
		}
		if (mass >= s[pos]) {
			mass += s[pos];
			pos = w[pos];
		}
		else {
			mass += p[pos];
			pos = l[pos];
		}
	}
	return mass;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 7 ms 9980 KB Output is correct
4 Correct 196 ms 242688 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 162 ms 242532 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 1827 ms 1936628 KB Output is correct
3 Correct 1469 ms 1938436 KB Output is correct
4 Correct 1426 ms 1939940 KB Output is correct
5 Correct 1479 ms 1939940 KB Output is correct
6 Correct 1502 ms 1938408 KB Output is correct
7 Correct 1442 ms 1936584 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 227 ms 244088 KB Output is correct
3 Execution timed out 7098 ms 243928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 227 ms 244088 KB Output is correct
3 Execution timed out 7098 ms 243928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 227 ms 244088 KB Output is correct
3 Execution timed out 7098 ms 243928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 1827 ms 1936628 KB Output is correct
3 Correct 1469 ms 1938436 KB Output is correct
4 Correct 1426 ms 1939940 KB Output is correct
5 Correct 1479 ms 1939940 KB Output is correct
6 Correct 1502 ms 1938408 KB Output is correct
7 Correct 1442 ms 1936584 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 227 ms 244088 KB Output is correct
10 Execution timed out 7098 ms 243928 KB Time limit exceeded
11 Halted 0 ms 0 KB -