Submission #780946

#	Time	Username	Problem	Language	Result	Execution time	Memory
780946		fatemetmhr	Rail (IOI14_rail)	C++17	100 / 100	52 ms	4556 KiB

rail

//  ~ Be Name Khoda ~  //

#include "rail.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int disA[maxn5], disB[maxn5], rev[maxn];
vector <pair<int, int>> av;



void findLocation(int n, int fir, int loc[], int ty[])
{

	memset(rev, -1, sizeof rev);
	loc[0] = fir;
	rev[fir] = 0;
	ty[0] = 1;
	if(n == 1)
		return;
	for(int i = 1; i < n; i++){
		disA[i] = getDistance(0, i);
		av.pb({disA[i], i});
	}
	sort(all(av));
	int C = -1, D = -1, B = av[0].se, A = 0;
	int last = 0;
	//cout << "hey " << A << ' ' << B << endl;
	for(auto p : av){
		//check(loc, ty, last);
		//cout << "ok " << last << ' ' << C << ' ' << D << ' ' << loc[last] << ' ' << ty[last] << endl;
		//cout << disA[last] << ' ' << disB[last] << endl;
		//if(last == 4855)
		//	exit(0);
		int v = p.se;
		last = v;
		if(v == B){
			loc[v] = loc[0] + disA[v];
			rev[loc[v]] = v;
			ty[v] = 2;
			continue;
		}
		disB[v] = getDistance(B, v);
		if(disA[v] == disB[v] + disA[B]){
			if(loc[B] - disB[v] > loc[A]){
				loc[v] = loc[B] - disB[v];
				rev[loc[v]] = v;
				ty[v] = 1;
				continue;
			}
			if(C == -1){
				C = v;
				loc[v] = loc[B] - disB[v];
				ty[v] = 1;
				rev[loc[v]] = v;
				continue;
			}
			int disC = getDistance(C, v);
			int ref = loc[C] + (disC + disB[C] - disB[v]) / 2;
			//if(v == 84)
			//	cout << ref << ' ' << rev[ref] << ' ' << ty[rev[ref]] << ' ' << disC << ' ' << disB[C] << ' ' << disB[v] << endl;
			if(rev[ref] != -1 && ty[rev[ref]] == 1){
				loc[v] = loc[C] + disC;
				ty[v] = 2;
				rev[loc[v]] = v;
			}
			else{
				loc[v] = loc[B] - disB[v];
				ty[v] = 1;
				if(loc[v] < loc[C])
					C = v;
				rev[loc[v]] = v;
			}
		}
		else{
			if(D == -1){
				D = v;
				loc[v] = loc[A] + disA[v];
				ty[v] = 2;
				rev[loc[v]] = v;
				continue;
			}
			int disD = getDistance(D, v);
			int ref = loc[A] + (disA[v] + disA[D] - disD) / 2;
			if(rev[ref] == -1 || ty[rev[ref]] == 1){
				loc[v] = loc[A] + disA[v];
				ty[v] = 2;
				rev[loc[v]] = v;
				if(loc[v] > loc[D])
					D = v;
			}
			else{
				loc[v] = loc[D] - disD;
				ty[v] = 1;
				rev[loc[v]] = v;
			}
		}
	}
	return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:46:6: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   46 |  int last = 0;
      |      ^~~~

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