Submission #1007080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007080		GrindMachine	Rail (IOI14_rail)	C++17	100 / 100	65 ms	98896 KiB

rail

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
http://blog.brucemerry.org.za/2014/07/ioi-2014-day-1-analysis.html

*/

const int MOD = 1e9 + 7;
const int N = 5e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "rail.h"

int dp[N][N];
int q = 0;
int currn;

int d(int i, int j){
	if(i == j) return 0;
	if(i > j) swap(i,j);
	if(dp[i][j] != -1){
		return dp[i][j];
	}
	q++;	
	// assert(q <= currn*(currn-1)/2);
	return dp[i][j] = getDistance(i,j);
}

void findLocation(int n, int first_loc, int location[], int stype[])
{
	rep(i,n){
		location[i] = -1;
		stype[i] = -1;
	}

	memset(dp,-1,sizeof dp);
	currn = n;

	location[0] = first_loc;
	stype[0] = 1;

	if(n == 1) return;

	// order by dis from first
	int first = 0;
	vector<pii> dis;
	rep(i,n){
		dis.pb({d(first,i),i});
	}

	sort(all(dis));

	// find the ()
	int first_close = dis[1].ss;
	location[first_close] = first_loc+dis[1].ff;
	stype[first_close] = 2;

	// find all to the left (path from first to i must pass through first_close)
	// guys not on left must be on right
	vector<pii> to_left, to_right;
	rep(i,n){
		if(i == first or i == first_close) conts;
		if(d(first,i) == d(first,first_close)+d(first_close,i)){
			to_left.pb({d(first_close,i),i});
		}
		else{
			to_right.pb({d(first,i),i});
		}
	}

	sort(all(to_left)), sort(all(to_right));

	auto find_station = [&](int pos){
		rep(i,n){
			if(location[i] == pos){
				return i;
			}
		}

		return -1;
	};

	// identify the types and locations of all guys to the left
	int l = first;
	
	for(auto [dis,i] : to_left){
		int val = d(l,i)+d(first_close,i)-d(l,first_close);
		assert(!(val&1));
		val /= 2;
		int pos = location[l]+d(l,i)-val;

		int station = find_station(pos);

		if(station != -1 and stype[station] == 1){
			location[i] = location[station]+val;
			stype[i] = 2;
		}
		else{
			location[i] = location[first_close]-d(first_close,i);
			stype[i] = 1;
			l = i;
		}
	}

	// identify the types and locations of all guys to the right
	int r = first_close;

	for(auto [dis,i] : to_right){
		int val = d(r,i)+d(first,i)-d(first,r);
		assert(!(val&1));
		val /= 2;
		int pos = location[r]-d(r,i)+val;

		int station = find_station(pos);

		if(station != -1 and stype[station] == 2){
			location[i] = location[station]-val;
			stype[i] = 1;
		}
		else{
			location[i] = location[first]+d(first,i);
			stype[i] = 2;
			r = i;
		}

		debug(i,stype[i],location[i]);
	}

	debug(first);
	debug(first_close);

	rep(i,n){
		debug(stype[i],location[i]);
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:46:20: warning: statement has no effect [-Wunused-value]
   46 | #define debug(...) 42
      |                    ^~
rail.cpp:175:3: note: in expansion of macro 'debug'
  175 |   debug(i,stype[i],location[i]);
      |   ^~~~~
rail.cpp:46:20: warning: statement has no effect [-Wunused-value]
   46 | #define debug(...) 42
      |                    ^~
rail.cpp:178:2: note: in expansion of macro 'debug'
  178 |  debug(first);
      |  ^~~~~
rail.cpp:46:20: warning: statement has no effect [-Wunused-value]
   46 | #define debug(...) 42
      |                    ^~
rail.cpp:179:2: note: in expansion of macro 'debug'
  179 |  debug(first_close);
      |  ^~~~~
rail.cpp:46:20: warning: statement has no effect [-Wunused-value]
   46 | #define debug(...) 42
      |                    ^~
rail.cpp:182:3: note: in expansion of macro 'debug'
  182 |   debug(stype[i],location[i]);
      |   ^~~~~

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