제출 #1139674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139674		mychecksedad	철로 (IOI14_rail)	C++20	100 / 100	64 ms	596 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>


void findLocation(int n, int f, int location[], int stype[]){
	if(n == 1){
		location[0] = f;
		stype[0] = 1;
		return;
	}
	vector<pii> d(n);
	vector<int> dist(n);
	for(int i = 1; i < n; ++i){
		d[i] = {getDistance(0, i), i};
		dist[i] = d[i].ff;
	}

	location[0] = f;
	stype[0] = 1;

	d[0] = {MOD, 0};
	sort(all(d));
	int R = d[0].ss, L = 0;
	
	location[R] = f + d[0].ff;
	stype[R] = 2;

	vector<int> dist2(n);

	for(int i = 1; i + 1 < n; ++i){
		int y = getDistance(d[0].ss, d[i].ss);
		dist2[d[i].ss] = y;
		int x = d[i].ff;
		if(x == y + dist[d[0].ss] && y < dist[d[0].ss]){ // inside
			location[d[i].ss] = location[d[0].ss] - y;
			stype[d[i].ss] = 1;
		}else if(x == y + dist[d[0].ss]){ // lefter
			int z = getDistance(d[i].ss, L);
			int LS = L;
			for(int j = 1; j < i; ++j){
				if(stype[d[j].ss] == 1 && location[0] > location[d[j].ss] && location[d[j].ss] < location[L] + z){
					if(location[LS] < location[d[j].ss]){
						LS = d[j].ss;
					}
				}
			}
			if(location[L] + z == location[LS] + (y - dist2[LS])){ // inside
				stype[d[i].ss] = 2;
				location[d[i].ss] = location[L] + z;
			}else{ // lefter
				location[d[i].ss] = location[d[0].ss] - y;
				stype[d[i].ss] = 1;
				L = d[i].ss;
			}
		}else{ // righer
			int z = getDistance(d[i].ss, R);

			int RS = R;
			for(int j = 1; j < i; ++j){
				if(stype[d[j].ss] == 2 && location[1] < location[d[j].ss] && location[d[j].ss] > location[R] - z){
					if(location[RS] > location[d[j].ss]){
						RS = d[j].ss;
					}
				}
			}

			if(location[R] - z == location[RS] - (x - dist[RS])){ // inside
				stype[d[i].ss] = 1;
				location[d[i].ss] = location[R] - z;
			}else{ // rigter
				location[d[i].ss] = f + x;
				stype[d[i].ss] = 2;
				R = d[i].ss;
			}
		}
	}
	// for(int j = 0; j < n; ++j) cout << stype[j] << ' ' << location[j] << '\n';
}

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