Submission #377008

#	Time	Username	Problem	Language	Result	Execution time	Memory
377008		crackersamdjam	Rail (IOI14_rail)	C++17	100 / 100	249 ms	1004 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;

// #ifdef LOCAL
// // int nn = 4, ss[] = {2, 5, 3, 1}, tt[] = {2, 0, 2, 2};
// // int nn = 4, ss[] = {4, 1, 9, 2}, tt[] = {1, 1, 2, 2};
// // int ffirst = ss[0];
// // int dd[4][4] = {{0, 13, 5, 14}, {13, 0, 8, 1}, {5, 8, 0, 9}, {14, 1, 9, 0}};
// int dd[10][10];
// int ss[10];
// int tt[10];
// int nn;

// int getDistance(int i, int j){
// 	assert(0 <= i and i < nn);
// 	assert(0 <= j and j < nn);
// 	return dd[i][j];
// }
// #else
// #include "rail.h"
// #endif

/*
15
7 7 1 1
1 1 1 1
9 9 2 2
2 2 1 1
-2 6 1 2
*/

void findLocation(int n, int first, int loc[], int stype[]){
	array<int, 2> dis[n];
	dis[0] = {0, 0};
	loc[0] = first;
	stype[0] = 1;

	for(int i = 1; i < n; i++){
		dis[i] = {getDistance(0, i), i};
	}
	sort(dis, dis+n);
	auto [add, fs] = dis[1];
	int l = 0, r = fs;
	loc[fs] = first+add;
	stype[fs] = 2;
	pr("fs", fs, loc[fs]);

	set<int> lc, rd;
	lc.insert(loc[0]);
	rd.insert(loc[fs]);

	for(int j = 2; j < n; j++){
		auto [d0, i] = dis[j];
		int df = getDistance(fs, i);
		pr(j, i, d0-add, df);
		if(d0-add == df){
			//then 0->i turns at fs
			// 0 ( 1
			// ( l 0 1
			// l ) 0 1
			if(df < add){
				// first case
				loc[i] = loc[fs]-df;
				stype[i] = 1;
				continue;
			}

			// now check it's distance from l to know which case (out of last two)
			int dl = getDistance(l, i);
			pr("ree", df, loc[fs]-loc[l], dl);

			assert(df <= loc[fs]-loc[l] + dl);

			int dif = (loc[fs]-loc[l] + dl - df)/2;

			if(lc.count(loc[l]+dif)){
				//it's l )
				loc[i] = loc[l]+dl;
				stype[i] = 2;
			}
			else{
				loc[i] = loc[fs]-df;
				stype[i] = 1;
				l = i;
				lc.insert(loc[i]);
			}

			// if(df == loc[fs]-loc[l] + dl){
			// 	//it's l )
			// 	loc[i] = loc[l]+dl;
			// 	stype[i] = 2;
			// }
			// else{
			// 	loc[i] = loc[fs]-df;
			// 	stype[i] = 1;
			// 	l = i;
			// }
		}
		else{
			//it doesn't turn at fs
			// 0 1 ( r
			// 0 1 r )
			int dr = getDistance(r, i);
			// assert(d0 >= loc[r]-loc[0] + dr);
			assert(d0 <= loc[r]-loc[0] + dr);
			
			int dif = (loc[r]-loc[0] + dr - d0)/2;

			if(rd.count(loc[r]-dif)){
				// 0 1 ( r
				loc[i] = loc[r]-dr;
				stype[i] = 1;
			}
			else{
				loc[i] = loc[0]+d0;
				stype[i] = 2;
				r = i;
				rd.insert(loc[i]);
			}

			// if(d0 == loc[r]-loc[0] + dr){
			// 	// 0 1 ( r
			// 	loc[i] = loc[r]-dr;
			// 	stype[i] = 1;
			// }
			// else{
			// 	loc[i] = loc[0]+d0;
			// 	stype[i] = 2;
			// 	r = i;
			// }
		}
		// dif = (d0 - (loc[r]-loc[0]) - dr)
		// if dif > 0, then it's somewhere on right
		// but if on right and dif = 0,
		// that means that d0 = dr + (loc[r]-loc[0])
		// let m be the point where r->i turns right
		// 0->m + m->r + r->i = dr + 0->m + m->r
		// r->i = dr
		// r->i = m<-r + m->r + r->i
		// m->r = 0]
		// so impossible
	}
}
/*
get all from station 0 and sort by distance
the first one is the first D right of 0
then loop through stations in sorted order,
compare dis(0, i) and dis(1st D, i) to see if on left or right side
then, to know if it's ( or ), query from most leftmost/rightmost existing one
*/

// #ifdef LOCAL
// int main(){
// 	// int locations[nn], stype[nn];
// 	cin>>nn;
// 	for(int i = 0; i < nn; i++){
// 		cin>>ss[i]>>tt[i];
// 	}


// 	int locations[nn], stype[nn];
// 	findLocation(nn, ss[0], locations, stype);

// 	for(int i = 0; i < nn; i++)
// 		cout<<locations[i]<<' ';
// 	cout<<'\n';
// 	for(int i = 0; i < nn; i++)
// 		cout<<stype[i]<<' ';
// 	cout<<'\n';	
// }
// #endif

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