제출 #1238727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238727		nikulid	추월 (IOI23_overtaking)	C++20	9 / 100	6 ms	584 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; // mp[m]{time} = speed
int x,m;
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;
	for(auto e:s){
		S.pb(e);
	}
	arrs = vector<set<ll>>(M);
	mp = 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;
	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";
		arrs[0].insert(cur_time);
		mp[0][cur_time] = max(mp[0][cur_time], cur_speed);
		for(int i=1; i<M; i++){
			derr<<"$ i="<<i<<"\n";
			// what time would we get there... (lower_bound-1)
			it = arrs[i-1].lower_bound(cur_time);
			if(it != arrs[i-1].begin()){ // if there is something below...
				it--;
				previous_time = *it;
				previous_speed = mp[i-1][previous_time];
				derr<<"$ if was met: ptime="<<previous_time<<", pspeed="<<previous_speed<<"\n";
			} else{
				previous_time = 0;
				previous_speed = 0;
			}
			derr<<"$ ifelse done.\n";
			if(cur_time + cur_speed*(s[i]-s[i-1]) < previous_time+previous_speed*(s[i]-s[i-1])){
				cur_time = previous_time+previous_speed*(s[i]-s[i-1]);
			} else{
				cur_time += cur_speed*(s[i]-s[i-1]);
			}
			arrs[i].insert(cur_time);
			mp[i][cur_time] = max(mp[i][cur_time], cur_speed);
		}
	}

	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<<"the slowest of these busses takes "<<mp[i][*it]<<" seconds to travel 1km.\n";
				cerr<<"\n";
			}
			cerr<<"\n";
		}	
	}


	return;
}

long long arrival_time(long long Y){
	ll cur_time = Y;
	ll cur_speed = x;
	ll previous_speed;
	ll previous_time;

	for(int i=1; i<m; i++){
		it = arrs[i-1].lower_bound(cur_time);
		if(it != arrs[i-1].begin()){ // if there is something below...
			it--;
			previous_time = *it;
			previous_speed = mp[i-1][previous_time];
			derr<<"$ if was met: ptime="<<previous_time<<", pspeed="<<previous_speed<<"\n";
		} else{
			previous_time = 0;
			previous_speed = 0;
		}
		if(cur_time + cur_speed*(S[i]-S[i-1]) < previous_time+previous_speed*(S[i]-S[i-1])){
			cur_time = previous_time+previous_speed*(S[i]-S[i-1]);
		} else{
			cur_time += cur_speed*(S[i]-S[i-1]);
		}
	}

	return cur_time;
}

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