제출 #1216291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216291		thelegendary08	던전 (IOI21_dungeons)	C++17	0 / 100	7093 ms	2162688 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
using namespace std;
const int lg = 16;
vector<signed> s,p,w,l; int n; vi type;
vector<vector<vpii>> jmp; vi rngs;
void init(signed n, std::vector<signed> s, std::vector<signed> p, std::vector<signed> w, std::vector<signed> l) {
	::s=s; ::p=p; ::w=w; ::l=l; ::n=n;
	set<int>si;
	f0r(i,n){
		si.insert(s[i]);
	}
	for(auto u : si){
		rngs.pb(u);
	}
	type.resize(n);
	f0r(i,n){
		f0r(j, rngs.size()){
			if(rngs[j] == s[i]){
				type[i] = j;
			}
		}
	}
	
	vi tmp(n);
	jmp.resize(n);
	f0r(i,n){
		jmp[i].resize(lg);
		f0r(j, lg){
			jmp[i][j].resize(rngs.size() + 1);
		}
	}
	f0r(i,rngs.size() + 1){
		f0r(j, n){
			if(tmp[j]){
				jmp[j][0][i] = mp(w[j],s[j]);
			}
			else{
				if(i == 0 && j == 0){
					// dout2(l[j], p[j]);
				}
				jmp[j][0][i] = mp(l[j],p[j]);
			}
		}
		// dout2(jmp[0][0][0].first, jmp[0][0][0].second);
		FOR(j, 1, lg){
			f0r(k, n){
				if(jmp[k][j-1][i].first == n)jmp[k][j][i] = jmp[k][j-1][i];
				else jmp[k][j][i] = mp(jmp[jmp[k][j-1][i].first][j-1][i].first, jmp[k][j-1][i].second + jmp[jmp[k][j-1][i].first][j-1][i].second);
			}
		}
		if(i != rngs.size()){
			f0r(j,n){
				if(type[j] == i)tmp[j] = 1;
			}
		}
	}
	
	// dout2(jmp[0][0][0].first, jmp[0][0][0].second);
	
	return;
}

long long simulate(signed x, signed z) {
	int cur = x;
	int a = z;
	int curtype = 0;
	int nxt = 4e18;
	int ptr = rngs.size();
	int cnt = 0;
	for(auto u : rngs){
		if(a >= u)curtype++;
		else{
			ptr = cnt;
			nxt = u; break;
		}
		cnt++;
	}
	
	while(cur != n){
		// dout(curtype);
		for(int i = lg - 1; i>=0; i--){
			if(a + jmp[cur][i][curtype].second < nxt){
				a += jmp[cur][i][curtype].second;
				cur = jmp[cur][i][curtype].first;
				// cout<<a<<' '<<cur<<"SEDF"<<endl;
			}
			if(cur == n)break;
		}
		if(cur == n)break;
		// cout<<a<<' '<<cur<<endl;
		// dout2(jmp[cur][0][curtype].first, jmp[cur][0][curtype].second);
		a += jmp[cur][0][curtype].second;
		cur = jmp[cur][0][curtype].first;
		// cout<<a<<' '<<cur<<endl;
		// vout(rngs);
		while(ptr != rngs.size() && rngs[ptr] < a){
			ptr++; curtype++;
		}
	}
	
	return a;
}

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