Submission #857809

#	Time	Username	Problem	Language	Result	Execution time	Memory
857809		sunwukong123	Rail (IOI14_rail)	C++14	100 / 100	54 ms	1348 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 5005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<pi> vec;
int D[MAXN];
map<int,int>tt;
void findLocation(int n, int first, int loc[], int stype[])
{
	for(int i=1;i<n;i++){
		D[i]=getDistance(0,i);
		vec.push_back({D[i],i});
	}
	sort(vec.begin(),vec.end());
	stype[0]=tt[0]=1;
	stype[vec[0].second]=tt[vec[0].first]=2;
	loc[vec[0].second]=vec[0].first;
	int R=vec[0].second;
	int L=0;
	for(int i=1;i<(int)vec.size();i++){
		int idx=vec[i].second;
		int d1=getDistance(idx,R);
		int d2=getDistance(idx,L);
		//debug(vec[i].second,d1,d2);
		bool c1=0,c2=0;
		int ww=loc[R]-d1;
		int p=ww+(D[idx]-ww)/2;
		if(ww<0){
			p=(D[idx]-abs(ww))/2;
		}
		if(tt[ww] == 0 && ((D[idx]-abs(ww)) % 2 == 0) && (D[idx]-abs(ww)>0) && tt[p] == 2){
			c1=1;
		}

		ww=loc[L]+d2;
		int dd=D[idx]-2*vec[0].first;
		p=ww-(dd-abs(ww))/2;
		if(tt[ww] == 0 && ww<0 && (dd-abs(ww))%2 == 0 && (dd-abs(ww))>0 && tt[p]==1){
			c2=1;
		}
		//debug(c1,c2);
		if(c1&&!c2){
			loc[idx]=loc[R]-d1;
			stype[idx] = tt[loc[idx]] = 1;
			if(loc[idx] < loc[L])L=idx;
		}
		if(!c1&&!c2){
			loc[idx]=loc[L]+d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}
		if(c1&&c2){
			loc[idx]=loc[L] + d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}
		if(!c1 && c2){
			loc[idx]=loc[L] + d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}

	}
	
	for(int i=0;i<n;i++){
		loc[i]+=first;
	}
	/*
	for(int i=0;i<n;i++){
		cerr<<stype[i]<<" ";
	}
	cerr<<"\n";
	for(int i=0;i<n;i++){
		cerr<<loc[i]<<" ";
	}
	cerr<<"\n\n\n";
	*/
}

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