Submission #857790

#	Time	Username	Problem	Language	Result	Execution time	Memory
857790		sunwukong123	Rail (IOI14_rail)	C++14	0 / 100	48 ms	912 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;
	set<int>s;
	int L=0;
	for(int i=1;i<n;i++){
		int d1=getDistance(vec[i].second,R);
		int d2=getDistance(vec[i].second,L);
		bool c1=0,c2=0;
		int ww=loc[R]-d1;
		int p=ww+(D[i]-ww)/2;
		if(ww<0){
			p=(D[i]-abs(ww))/2;
		}
		if(((D[i]-abs(ww)) % 2 == 0) && (D[i]-abs(ww)>0) && tt[p] == 2){
			c1=1;
		}

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

	}
	
	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: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44