제출 #779438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779438		NothingXD	Rail (IOI14_rail)	C++17	30 / 100	47 ms	516 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e3 + 10;

int n, val[maxn], idx[maxn];
vector<int> v;
bool cmp(int x, int y){
	return val[x] < val[y];
}

void findLocation(int N, int first, int loc[], int type[]){
	n = N;
	for (int i = 1; i < n; i++){
		idx[i] = i;
		val[i] = getDistance(0, i);
	}
	sort(idx + 1, idx + n, cmp);
	loc[0] = first;
	loc[idx[1]] = first + val[idx[1]];
	type[0] = 1;
	type[idx[1]] = 2;
	v.push_back(0);
	v.push_back(idx[1]);
	for (int i = 2; i < n; i++){
		int l = v[0], r = v.back();
		int x = getDistance(l, idx[i]);
		int y = getDistance(r, idx[i]);
		int z = loc[r] - loc[l];
		int tmp = x + y - z;
		if (tmp & 1) return;
		tmp >>= 1;
		int rng = loc[l] + x - tmp;
		for (auto u: v){
			if (loc[u] == rng){
				if (type[u] == 1){
					loc[idx[i]] = rng + tmp;
					type[idx[i]] = 2;
				}
				else{
					loc[idx[i]] = rng - tmp;
					type[idx[i]] = 1;
				}
			}
		}
		vector<int> v2;
		bool flg = false;
		for (auto u: v){
			assert(loc[u] != loc[idx[i]]);
			if (loc[u] >= loc[idx[i]] && flg == false){
				v2.push_back(idx[i]);
				flg = true;
			}
			v2.push_back(u);
		}
		if (flg == false) v2.push_back(idx[i]);
		v = v2;
	}
}

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