Submission #585976

#	Time	Username	Problem	Language	Result	Execution time	Memory
585976		SeDunion	Rail (IOI14_rail)	C++17	30 / 100	83 ms	768 KiB

rail

#include "rail.h"
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 5055;
const int inf = 1e9;

int n, d0[N];

#define cout if(false)cout

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	vector<pair<int,int>>v;
	for (int i = 1 ; i < n ; ++ i) {
		d0[i] = getDistance(0, i);
		v.emplace_back(d0[i], i);
	}
	sort(v.begin(), v.end());
	int L = 0, R = v[0].second;
	stype[0] = 1, location[0] = first;
	stype[R] = 2, location[R] = first + v[0].first;
	set<int>LL,RR;
	int dlr = v[0].first;
	for (int i = 1 ; i < (int)v.size() ; ++ i) {
		LL.insert(location[L]);
		RR.insert(location[R]);
		int di = v[i].first, k = v[i].second;
		int dl = getDistance(L, k);
		int dr = getDistance(R, k);
		int X = location[L];
		int Y = location[R];
		int Z = Y - dr;
		cout << X << " " << Y << " | " << dl << " " << dr << endl;
		if (Z < X) {
			int D = X - Z;
			int C = dl - D;
			if (C % 2 == 0) {
				C /= 2;
				C = X + C;
				if (*RR.lower_bound(X) == C) {
					stype[k] = 1;
					location[k] = Z;
					L = k;
					continue;
				}
			}
		} else {
			int D = Z - X;
			int C = dl - D;
			if (C % 2 == 0) {
				C /= 2;
				C = X + dl - C;
				if (*RR.lower_bound(Z) == C) {
					stype[k] = 1;
					location[k] = Z;
					LL.insert(location[k]);
					continue;
				}
			}
		}
		Z = X + dl;
		if (Y < Z) {
					stype[k] = 2;
					location[k] = Z;
					R = k;
					continue;

			int D = Z - Y;
			int C = dr - D;
			if (C % 2 == 0) {
				C /= 2;
				C = Y - C;
				if (*prev(LL.upper_bound(Y)) == C) {
					stype[k] = 2;
					location[k] = Z;
					R = k;
					continue;
				}
			}
		} else {
					stype[k] = 2;
					location[k] = Z;
					RR.insert(location[k]);
					continue;
			int D = Y - Z;
			int C = dr - D;
			if (C % 2 == 0) {
				C /= 2;
				C = Y - dr + C;
				if (*prev(LL.upper_bound(Z)) == C) {
					stype[k] = 2;
					location[k] = Z;
					RR.insert(location[k]);
					continue;
				}
			}
		}
	}
	for (int i = 0 ; i < n ; ++ i) {
		cout << stype[i] << " " << location[i] << endl;
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:32:7: warning: unused variable 'di' [-Wunused-variable]
   32 |   int di = v[i].first, k = v[i].second;
      |       ^~
rail.cpp:28:6: warning: unused variable 'dlr' [-Wunused-variable]
   28 |  int dlr = v[0].first;
      |      ^~~

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