Submission #754678

#	Time	Username	Problem	Language	Result	Execution time	Memory
754678		tolbi	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7074 ms	239020 KiB

dungeons

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulHamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename T> vector<int32_t> normalize(vector<T> &rt){vector<int32_t> arr(rt.size());for (int i = 0; i < rt.size(); i++){arr[i]=rt[i];}return arr;}
#define endl '\n'
#define int long long
#define vint(x) vector<int> x
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define tol(bi) (1LL<<((int)(bi)))
#define lsb(x) (x&-x)
const int MOD = 1e9+7;
const int64_t INF = LONG_LONG_MAX;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "dungeons.h"
vector<vector<int>> st;
vector<vector<int>> stc;
vector<int32_t> s,p,w,l;
set<int> kum;
int n, LOG;
void init(int32_t _n, vector<int32_t> _s, vector<int32_t> _p, vector<int32_t> _w, vector<int32_t> _l) {
	n=_n+1;
	s=_s,p=_p,w=_w,l=_l;
	LOG=30;
	for (int i = 0; i < s.size(); ++i)
	{
		kum.insert(s[i]);
	}
	st.resize(n,vector<int>(LOG));
	stc.resize(n,vector<int>(LOG));
	st[n-1][0]=-1;
	stc[n-1][0]=23;
}
int sum(int a, int b){
	if (b>=INF-a) return INF;
	return a+b;
}
void construct(int val){
	for (int i = 0; i < n-1; i++){
		if (val>=s[i]){
			st[i][0]=w[i];
			stc[i][0]=s[i];
		}
		else {
			st[i][0]=l[i];
			stc[i][0]=p[i];
		}
	}
	for (int bit = 1; bit < LOG; bit++){
		for (int node = 0; node < n; node++){
			if (st[node][bit-1]==-1) {
				st[node][bit]=-1;
				stc[node][bit]=23;
				continue;
			}
			st[node][bit]=st[st[node][bit-1]][bit-1];
			stc[node][bit]=sum(stc[node][bit-1],stc[st[node][bit-1]][bit-1]);
		}
	}
}
pair<int,int> kthpar(int node, int kal){
	int cur = 0;
	for (int bit = LOG-1; bit >= 0; bit--){
		if (st[node][bit]==-1) continue;
		if (kal!=-1 && stc[node][bit]>=kal) continue;
		kal-=stc[node][bit];
		cur+=stc[node][bit];
		node=st[node][bit];
	}
	return {node,cur};
}
int64_t simulate(int32_t x, int32_t z) {
	if (x==n-1) return z;
	construct(z);
	pair<int,int> gt;
	if (kum.lower_bound(z+1)==kum.end()){
		gt = kthpar(x,-1);
	}
	else {
		gt = kthpar(x,*kum.lower_bound(z+1)-z);
	}
	z+=gt.second;
	x=gt.first;
	if (gt.first!=n-1){
		z+=stc[x][0];
		x=st[x][0];
	}
	return simulate(x,z);
}

Compilation message (stderr)

dungeons.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
dungeons.cpp: In function 'void init(int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < s.size(); ++i)
      |                  ~~^~~~~~~~~~

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