Submission #283399

#	Time	Username	Problem	Language	Result	Execution time	Memory
283399		rqi	Rail (IOI14_rail)	C++14	30 / 100	89 ms	640 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)

const int MOD = 1000000007;
const int mx = 5005;
int pos1[mx];
int pos2[mx];

void findLocation(int N, int first, int location[], int stype[])
{
	stype[0] = 1;
	location[0] = 0;
	pi mn = mp(MOD, -1);

	for(int i = 1; i < N; i++){
		pos1[i] = getDistance(0, i);
		mn = min(mn, mp(pos1[i], i));
	}

	stype[mn.s] = 2;
	location[mn.s] = mn.f;

	pi c = mp(mn.f, 0); //distance from mn.s

	for(int i = 1; i < N; i++){
		if(i == mn.s) continue;
		pos2[i] = getDistance(mn.s, i);
		c = min(c, mp(pos2[i], i));
	}
	c.f = mn.f-c.f; //position

	//cout << mn.f << " " << mn.s << " " << c.f << " " << c.s << "\n";

	stype[c.s] = 1;
	location[c.s] = c.f;

	vpi lefs; //distance from a1, index
	vpi rigs; //distance from 0, index

	for(int i = 1; i < N; i++){
		if(i == mn.s || i == c.s) continue;
		int diff = pos1[i]-pos2[i];
		if(diff == mn.f){ //left of a1
			lefs.pb(mp(pos2[i], i));
		}
		else{ //right of a1
			rigs.pb(mp(pos1[i], i));
		}
	}

	sort(all(lefs));
	sort(all(rigs));

	// cout << "lefs: \n";
	// for(auto u: lefs){
	// 	cout << u.f << " " << u.s << "\n";
	// }
	// cout << "rigs: \n";
	// for(auto u: rigs){
	// 	cout << u.f << " " << u.s << "\n";
	// }
	// cout << "\n";

	pi cur = mp(mn.f, 0); //distance, index of current furthest

	for(auto u: lefs){
		if(u.f < mn.f){
			stype[u.s] = 1;
			location[u.s] = mn.f-u.f;
			continue;
		}
		if(u.f != cur.f+getDistance(cur.s, u.s)){
			stype[u.s] = 1;
			location[u.s] = mn.f-u.f;
			cur = u;
		}
		else{
			stype[u.s] = 2;
			location[u.s] = mn.f-cur.f+(u.f-cur.f);
		}
	}
	cur = mp(mn.f, mn.s);
	for(auto u: rigs){
		if(u.f != cur.f+getDistance(cur.s, u.s)){
			stype[u.s] = 2;
			location[u.s] = u.f;
			cur = u;
		}
		else{
			stype[u.s] = 1;
			location[u.s] = cur.f-(u.f-cur.f);
		}
	}

	for(int i = 0; i < N; i++){
		location[i]+=first;
		//cout << location[i] << "\n";
	}

	// stype[0] = 1;
	// location[0] = first;
	
	// pi mn = mp(MOD, -1);
	// for(int i = 1; i < N; i++){
	// 	pos1[i] = getDistance(0, i);
	// 	mn = min(mn, mp(pos1[i], i));
	// }

	// stype[mn.s] = 2;
	// location[mn.s] = first+mn.f;

	// for(int i = 1; i < N; i++){
	// 	if(i == mn.s) continue;
	// 	pos2[i] = getDistance(mn.s, i);
	// }

	// for(int i = 1; i < N; i++){
	// 	if(i == mn.s) continue;
	// 	if(pos1[i] > pos2[i]){
	// 		stype[i] = 1;
	// 		location[i] = first-(pos1[i]-2*mn.f);
	// 	}
	// 	else{
	// 		stype[i] = 2;
	// 		location[i] = first+pos1[i];
	// 	}
	// }


	// stype[0] = 1;
	// location[0] = first;
	// for(int i = 1; i < N; i++){
	// 	stype[i] = 2;
	// 	location[i] = location[0]+getDistance(0, i);
	// }
}

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