Submission #138503

#	Time	Username	Problem	Language	Result	Execution time	Memory
138503		jangwonyoung	Rail (IOI14_rail)	C++14	100 / 100	90 ms	4600 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int c,d;
int a[5001],b[5001];
int qc[5001],qd[5001];
int loc[1000001];
vector<int>l,r;
stack<int>s;
bool cmp(int x,int y){
	return qc[x]<qc[y];
}
void findLocation(int N, int first, int location[], int stype[]){
	n=N;
	for(int i=0; i<n ;i++){
		a[i]=b[i]=qc[i]=qd[i]=0;
	}
	l.clear();r.clear();
	c=0;a[c]=first;b[c]=1;loc[a[c]]=1;
	int d=1;
	for(int i=0; i<n ;i++){
		if(i!=c) qc[i]=getDistance(c,i);
		if(i!=c && qc[i]<qc[d]) d=i;
	}
	a[d]=a[c]+qc[d];b[d]=2;loc[a[d]]=2;
	for(int i=0; i<n ;i++){
		if(i==c) qd[i]=qc[d];
		else if(i!=d) qd[i]=getDistance(d,i);
		if(i!=d && qd[i]<qd[c]) c=i;
	}
	for(int i=0; i<n ;i++) if(i!=0 && i!=c) qc[i]-=qd[0]-qd[c];
	swap(qc[0],qc[c]);
	a[c]=a[d]-qd[c];b[c]=1;loc[a[c]]=1;
	for(int i=0; i<n ;i++){
		if(i==c || i==d) continue;
		if(qc[i]>qd[i]) l.push_back(i);
		else r.push_back(i);
	}
	s.push(c);
	sort(l.begin(),l.end(),cmp);
	for(auto x:l){
		if(x==l[0]){
			a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
			s.push(x);
			continue;
		}
		int y=s.top();
		int dis=getDistance(y,x);
		int r=(qd[y]+dis-qd[x])/2+a[y];
		if(loc[r]!=1){
			a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
			s.push(x);
		}
		else{
			a[x]=a[y]+dis;b[x]=2;loc[a[x]]=2;
		}
	}
	while(!s.empty()) s.pop();
	sort(r.begin(),r.end(),cmp);
	s.push(d);
	for(auto x:r){
		if(x==r[0]){
			a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
			s.push(x);
			continue;
		}
		int y=s.top();
		int dis=getDistance(y,x);
		int r=a[y]-(qc[y]+dis-qc[x])/2;
		if(loc[r]!=2){
			a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
			s.push(x);
		}
		else{
			a[x]=a[y]-dis;b[x]=1;loc[a[x]]=1;
		}
		
	}
	for(int i=0; i<n ;i++) loc[a[i]]=0;
	for(int i=0; i<n ;i++) location[i]=a[i],stype[i]=b[i];
}

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