제출 #1301626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301626		vtnoo	철로 (IOI14_rail)	C++20	100 / 100	32 ms	856 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN=5005,MAXM=1e6+5,INF=1e9;
int d0[MAXN];
map<int,int>m;
void findLocation(int N, int first, int location[], int stype[])
{
	stype[0]=1;location[0]=first;
	if(N==1)return;
	vector<pair<int,int>>v;
	fore(i,1,N){
		d0[i]=getDistance(0,i);
		v.emplace_back(d0[i],i);
	}
	sort(ALL(v));
	stype[v[0].snd]=2;location[v[0].snd]=first+v[0].fst;
	pair<int,int>X={0,location[0]},Y={v[0].snd,location[v[0].snd]};
	m[first]=1;m[Y.snd]=2;
	v.erase(v.begin());
	for(auto[d,Z]:v){
		int yz=getDistance(Y.fst,Z),xz=getDistance(X.fst,Z),xy=(Y.snd-X.snd),p=Y.snd+(xz-xy-yz)/2,type=m.find(p)==m.end()?(first<p?1:2):m[p];
		stype[Z]=(type==1?2:1);
		if(stype[Z]==1){
			location[Z]=location[Y.fst]-yz;
			m[location[Z]]=stype[Z];
			if(X.snd>location[Z]){
				X={Z,location[Z]};
			}
		}else{
			location[Z]=location[X.fst]+xz;
			m[location[Z]]=stype[Z];
			if(Y.snd<location[Z]){
				Y={Z,location[Z]};
			}
		}
	}
	return;
}

/*
 * o puede ser:
 * (  (  )  )
 * X  Z  p  Y
 * (  (  )   ) 
 * X  p  Y   Z */

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