Submission #588636

#	Time	Username	Problem	Language	Result	Execution time	Memory
588636		Tekor	Rail (IOI14_rail)	C++17	100 / 100	172 ms	30080 KiB

rail

#include "rail.h"
/*


*/
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define en '\n'
const int N = 5e3 + 100;
const int INTmx = (int)1e9;
int a[N],b[N],n;
bool ban[N];
int sd[N];
bool was[N][N];
int c[N][N];
int get(int x,int y) {
	if(was[x][y])return c[x][y];
	was[x][y] = 1;
	c[x][y] = getDistance(x,y);
	return c[x][y];
}
void findLocation(int NN, int first, int location[], int stype[]) {
	n = NN;
	location[0] = first;
	stype[0] = 1;
	pii mn = mp(INTmx,0);
	int L = 0;
	ban[0] = 1;
	for(int i = 1;i < n;i++) {
		if(ban[i])continue;
		mn = min(mn,mp(get(L,i),i));
	}
	int R = mn.s;
	ban[R] = 1;
	location[R] = location[L] + get(L,R);
	stype[R] = 2;
	int kol = 2;
	int lastR = location[L],lastL = location[R];
	for(int i = 1;i < n;i++) {
		if(ban[i])continue;
		if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
			stype[i] = 1;
			location[i] = location[R] - get(R,i);
			ban[i] = 1;
			lastR = max(lastR,location[i]);
			kol++;
		}
	}
	vector <int> exR,exL;
	exR.pb(R);
	exL.pb(L);
	//cout << R << " " << stype[R] << endl;
	while(kol < n) {
		mn = mp(INTmx,0);
		for(int i = 1;i < n;i++) {
			if(ban[i])continue;
			mn = min(mn,mp(get(exL[0],i),i));
		}
		int pos = mn.s;
		ban[pos] = 1;
		//cout << pos << " ? " << get(exL[0],pos) << " === " << get(exR[0],pos) << " - " << lastR - location[exL[0]] << " + " << location[exR[0]] - lastR << en;
		if(get(exL[0],pos) - (lastR - location[exL[0]]) + (location[exR[0]] - lastR) == get(exR[0],pos)) {
			int val = get(R,pos);
			int need = -1;
			for(int i = exR.size() - 2;i >= 0;i--) {
				if(val < location[R] - location[exR[i]]) {
					need = i;
					break;
				}
			}
			//cout << val << " " << need << " " << pos << en;
			if(need == -1) {
				exR.pb(pos);
				stype[pos] = 2;
				location[pos] = location[exL[0]] + get(exL[0],pos);
				kol++;
				R = pos;
				continue;
			}
			need++;
			if(get(exL[0],pos) == get(exL[0],R) + val - 2 * (location[R] - location[exR[need]])) {
				location[pos] = location[R] - val;
				stype[pos] = 1;
				kol++;
			}else {
				exR.pb(pos);
				kol++;
				stype[pos] = 2;
				location[pos] = location[exL[0]] + get(exL[0],pos);
				R = pos;
			}
		}else {
			int val = get(L,pos);
			int need = -1;
			for(int i = exL.size() - 2;i >= 0;i--) {
				if(val < location[exL[i]] - location[L]) {
					need = i;
					break;
				}
			}
			if(need == -1) {
				exL.pb(pos);
				stype[pos] = 1;
				location[pos] = location[exR[0]] - get(exR[0],pos);
				kol++;
				L = pos;
				continue;
			}
			need++;
			if(get(exR[0],pos) == get(exR[0],L) + val - 2 * (location[exL[need]] - location[L])) {
				location[pos] = location[L] + val;
				stype[pos] = 2;
				kol++;
			}else {
				exL.pb(pos);
				stype[pos] = 1;
				location[pos] = location[exR[0]] - get(exR[0],pos);
				kol++;
				L = pos;
			}
		}
		//cout << L << " " << R << endl;
	}
	
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:43:26: warning: unused variable 'lastL' [-Wunused-variable]
   43 |  int lastR = location[L],lastL = location[R];
      |                          ^~~~~

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