Submission #283413

#	Time	Username	Problem	Language	Result	Execution time	Memory
283413		rqi	Rail (IOI14_rail)	C++14	100 / 100	95 ms	636 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 bk back()
#define pb push_back
#define all(x) begin(x), end(x)
#define ins insert

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

void findLocation(int N, int first, int location[], int stype[])
{
	// cout << "B1\n";
	// cout.flush();
	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";
	// cout << "B2\n";
	// cout.flush();
	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 << "B3\n";
	// cout.flush();
	// 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; //distance, index of C
		cur = mp(mn.f, 0); 
		set<int> t;
		t.ins(cur.f);
		for(auto u: lefs){
			if(u.f < mn.f){
				stype[u.s] = 1;
				location[u.s] = mn.f-u.f;
				continue;
			}
			int d = getDistance(cur.s, u.s);
			int diff = u.f-d;
			bool case2 = 0;
			if((diff+cur.f) % 2 == 0 && t.count((diff+cur.f)/2)) case2 = 1;
			// for(auto x: cur){
			// 	if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
			// }
			if(case2){
				stype[u.s] = 2;
				location[u.s] = mn.f-cur.f+d;
			}
			else{
				stype[u.s] = 1;
				location[u.s] = mn.f-u.f;
				cur = u;
				t.ins(cur.f);
			}
			// if(u.f != cur.f+d){
			// 	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+d;
			// }
		}
	}
	


	{
		pi cur;
		cur = mp(mn.f, mn.s);
		set<int> t;
		t.ins(mn.f);
		for(auto u: rigs){
			int d = getDistance(cur.s, u.s);
			int diff = u.f-d;
			bool case2 = 0;
			if((diff+cur.f) % 2 == 0 && t.count((diff+cur.f)/2)) case2 = 1;
			// for(auto x: cur){
			// 	if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
			// }
			if(case2){
				stype[u.s] = 1;
				location[u.s] = cur.f-d;
			}
			else{
				stype[u.s] = 2;
				location[u.s] = u.f;
				cur = u;
				t.ins(cur.f);
			}

			// if(u.f != cur.f+d){
			// 	cout << u.f << " " << u.s << "\n";
			// 	stype[u.s] = 2;
			// 	location[u.s] = u.f;
			// 	cur = u;
			// }
			// else{
			// 	stype[u.s] = 1;
			// 	location[u.s] = cur.f-d;
			// }
		}
	}
	

	for(int i = 0; i < N; i++){
		location[i]+=first;
		//cout << stype[i] << " " << location[i] << "\n";
	}
	// cout << "B5\n";
	// cout.flush();
	// 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: 26 / 26
• Subtask 4: 44 / 44