제출 #1313481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313481		PlayVoltz	Rail (IOI14_rail)	C++20	100 / 100	34 ms	832 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

void findLocation(int n, int start, int loc[], int type[]){
	type[0]=1;
	loc[0]=start;
	if (n==1)return;
	vector<pii> ord;
	vector<int> dist(n, 0);
	for (int i=1; i<n; ++i)ord.pb(mp(dist[i]=getDistance(0, i), i));
	sort(ord.begin(), ord.end());
	type[ord[0].se]=2;
	loc[ord[0].se]=start+ord[0].fi;
	int l=0, r=ord[0].se;
	set<int> c, d;
	c.insert(start);
	d.insert(start+ord[0].fi);
	for (int i=1; i<ord.size(); ++i){
		int dl=getDistance(l, ord[i].se), dr=getDistance(r, ord[i].se);
		auto it=d.upper_bound(max(loc[r]-dr, loc[l]));
		if (it!=d.end()&&dl==abs(loc[r]-loc[l])+dr-2*abs(loc[r]-*it)){
			type[ord[i].se]=1;
			loc[ord[i].se]=loc[r]-dr;
			goto end;
		}
		it=c.lower_bound(min(loc[l]+dl, loc[r]));
		if (it!=c.begin()){
			--it;
			if (dr==abs(loc[r]-loc[l])+dl-2*abs(loc[l]-*it)){
				type[ord[i].se]=2;
				loc[ord[i].se]=loc[l]+dl;
				goto end;
			}
		}
		loc[ord[i].se]=dist[ord[i].se]+start;
		if (loc[ord[i].se]==dl+loc[l])type[ord[i].se]=2;
		else loc[ord[i].se]=loc[r]-dr, type[ord[i].se]=1;
		end:;
		if (type[ord[i].se]==1)c.insert(loc[ord[i].se]);
		if (type[ord[i].se]==2)d.insert(loc[ord[i].se]);
		if (type[ord[i].se]==1&&loc[ord[i].se]<loc[l])l=ord[i].se;
		if (type[ord[i].se]==2&&loc[ord[i].se]>loc[r])r=ord[i].se;
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44