제출 #1238756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238756		nikulid	추월 (IOI23_overtaking)	C++20	0 / 100	0 ms	328 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

bool debug=0;


#define ll long long
#define pb push_back
#define MP make_pair
#define derr if(debug)cerr
#define plist(x) if(debug){cerr<<"plist "<<#x<<":\n";for(auto e:x){cerr<<e<<" ";}cerr<<"\n";}

vector<set<ll>> arrs; // arr[m] = {timeA, timeB, ...} // (arrs = arrivals)
vector<map<ll, ll>> mp, goes_to; // mp[m]{time} = speed
int x,m,l;
vector<ll> S;
set<ll>::iterator it;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> s){
	m=M;
	x=X;
	l=L;
	for(auto e:s){
		S.pb(e);
	}
	arrs = vector<set<ll>>(M);
	mp = vector<map<ll, ll>>(M);
	goes_to = vector<map<ll, ll>>(M);

	// note that S is already sorted
	vector<pair<ll, ll>> ns;
	for(int i=0; i<N; i++){
		ns.pb(MP(W[i], T[i]));
	}
	sort(ns.begin(), ns.end());
	reverse(ns.begin(), ns.end());
	// ns is now sorted in order of slowest-to-fastest busses.
	vector<ll> dtime,speeds;
	for(int i=0; i<N; i++){
		speeds.pb(ns[i].first);	
		dtime.pb(ns[i].second);
	}
	pair<ll, ll> cpair;
	ll cur_time, cur_speed;
	ll previous_time, previous_speed;
	ll lower_goto, val;
	for(int b=0; b<N; b++){
		derr<<"$ b="<<b<<": ";
		cur_time = dtime[b];
		cur_speed = speeds[b];
		derr<<"$ bus with speed "<<cur_speed<<" and dtime "<<cur_time<<"\n";
		for(int i=0; i<M-1; i++){
			derr<<"$ i="<<i<<"\n";
			// what time would we get to the next... (lower_bound-1)
			it = arrs[i].lower_bound(cur_time);
			if(it != arrs[i].begin()){ // if there is indeed something below...
				it--;
				val = *it;
				lower_goto= goes_to[i][val];
			} else{
				lower_goto= 0;
			}
			arrs[i].insert(cur_time);

			previous_time = cur_time;
			cur_time = max(lower_goto, cur_time+cur_speed*(s[i+1]-s[i]));
			derr<<"$ cur_time = "<<cur_time<<"\n";
			derr<<"$ previous_time = "<<previous_time<<"\n";
			// below line causes issues (!)
			if(goes_to[i].find(previous_time) != goes_to[i].end()){
				derr<<"$ if..\n";
				goes_to[i][previous_time] = max(goes_to[i][previous_time], cur_time);
			} else{
				derr<<"$ else..\n";
				goes_to[i][previous_time] = cur_time;
			}
		}
	}

	if(debug)
	{
		
		for(int i=0; i<M; i++){
			cerr<<"\tfor the sorting station at d="<<s[i]<<":\n";	
			for(set<ll>::iterator it = arrs[i].begin(); it != arrs[i].end(); it++){
				cerr<<"some busses will stop here at t="<<*it<<"\n";
				cerr<<"running into any of these will make you goto: "<<goes_to[i][*it]<<"\n";
				cerr<<"\n";
			}
			cerr<<"\n";
		}	
	}


	return;
}

map<ll, ll> answered;
int to_answer;
long long arrival_time(long long Y){
	ll cur_time = Y;
	ll cur_speed = x;
	ll lower_goto, val;
	
	if(cur_time <= *(arrs[0].begin()))return l*x;
	// i=0 
	it = arrs[0].lower_bound(cur_time);
	it--;
	lower_goto= goes_to[0][*it];
	
	if(answered[lower_goto]) return answered[lower_goto];
	else to_answer = lower_goto;

	cur_time = max(lower_goto, cur_time+cur_speed*(S[1]-S[0]));
	// ---
	for(int i=1; i<m-1; i++){
		it = arrs[i].lower_bound(cur_time);
		if(it != arrs[i].begin()){ // if there is indeed something below...
			it--;
			val = *it;
			lower_goto= goes_to[i][val];
		} else{
			lower_goto= 0;
		}
		cur_time = max(lower_goto, cur_time+cur_speed*(S[i+1]-S[i]));
	}
	answered[to_answer] = cur_time;
	return cur_time;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35