제출 #429195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429195		Antekb	Rail (IOI14_rail)	C++14	30 / 100	87 ms	900 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
int dist[10000];
void findLocation(int N, int first, int location[], int stype[])
{
	for(int i=1; i<N; i++)dist[i]=getDistance(0, i);
	vector<int> V(N-1);
	iota(V.begin(), V.end(), 1);
	sort(V.begin(), V.end(), [](int a, int b){return dist[a]<dist[b];});
	location[0]=first;
	location[V[0]]=first+dist[V[0]];
	stype[0]=1;
	stype[V[0]]=2;
	int L=0, R=V[0];
	vector<int> C={location[0]}, D={location[V[0]]};
	for(int i=1; i<N-1; i++){
		int d1=getDistance(L, V[i]), d2=getDistance(R, V[i]);
		int loc=location[L]+d1;
		int t=-1;
		for(int j:C)if(j>t && j<loc)t=j;
		if(loc-t+location[R]-t==d2){
			if(loc<first){
				if(dist[V[i]]==dist[V[0]]+location[V[0]]-loc){
					location[V[i]]=loc;
					stype[V[i]]=2;
					D.push_back(loc);
				}
			}
			else{
				if(loc-first==dist[V[i]]){
					location[V[i]]=loc;
					stype[V[i]]=2;
					D.push_back(loc);
					if(loc>location[R])R=V[i];
				}
			}
		}
		loc=location[R]-d2;
		t=1e9;
		for(int j:D)if(j<t && j>loc)t=j;
		if(!stype[V[i]]){
			assert(t-loc+t-location[L]==d1);
			if(loc>first){
				assert(t-loc+t-first==dist[V[i]]);
				location[V[i]]=loc;
				stype[V[i]]=1;
				C.push_back(loc);
			}
			else{
				assert(dist[V[0]]+location[V[0]]-loc==dist[V[i]]);
				location[V[i]]=loc;
				stype[V[i]]=1;
				C.push_back(loc);
				if(loc<location[L])L=V[i];
			}
		}
		assert(stype[V[i]]);
	}
}

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