Submission #130367

#	Time	Username	Problem	Language	Result	Execution time	Memory
130367		antimirage	Rail (IOI14_rail)	C++14	100 / 100	93 ms	760 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 5005; 
 
int dist[2][N], first;
 
vector <int> lft, op, cl;
 
bool cmp1 (int a, int b) {
	return dist[0][a] < dist[0][b];
}
void findLocation(int n, int pos, int a[], int t[])
{
	int mn = 1e9 + 7, ind;
	a[0] = pos, t[0] = 1;
	
	for (int i = 1; i < n; i++) {	
		dist[0][i] = getDistance(0, i);
		if (dist[0][i] < mn) {
			mn = dist[0][i];
			ind = i;
		}
	//	cout << i << " -> " << dist[0][i] << endl;
	}
	a[ind] = pos + mn; t[ind] = 2;
	
	int L = 0, R = ind;
	
	for (int i = 1; i < n; i++) {
		if (i == ind) continue;
		lft.pb(i);
	}
	sort(all(lft), cmp1);
	
	op.pb(L);
	cl.pb(R);
	
	for (auto it : lft) {
	//	cout << it << endl;
		int res1 = getDistance(L, it);
		int res2 = getDistance(R, it);
		pos = a[L] + res1;
		
		if (pos < a[0]) {
			for (auto i : op) {
				if (a[i] < pos && res2 == (a[R] - a[i]) + pos - a[i]) {
					a[it] = pos;
					t[it] = 2;
					cl.pb(it);
					break;
				}
			}
		}
		if (t[it]) continue;
			
		pos = a[R] - res2;
		
		if (pos > a[0]) {
			for (auto i : cl) {
				if (a[i] > pos && res1 == (a[i] - a[L]) + a[i] - pos) {
					a[it] = pos;
					t[it] = 1;
					op.pb(it);
					break;
				}
			}
		}
		if (t[it]) continue;
		
		if (dist[0][it] == dist[0][ind] + a[ind] - pos) {
			op.pb(it);
			t[it] = 1;
			a[it] = pos;
			L = it;
		} else {
			cl.pb(it);
			t[it] = 2;
			a[it] = a[L] + res1;
			R = it;
		}
	}
	/**cout << "\nasd\n";
	for (int i = 0; i < n; i++) {
		cout << i << " ==> " << a[i] << " " << t[i] << endl;
	}**/
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:34:7: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  a[ind] = pos + mn; t[ind] = 2;
       ^

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