제출 #622552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
622552		balbit	철로 (IOI14_rail)	C++14	100 / 100	127 ms	98688 KiB

rail

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

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;
const int maxn = 3e5+5;

int got[5005][5005];
int n;

inline int RV(int x) {
	return n-1-x;
}

bool OPP=0;

inline int dis(int a, int b) {
	if (OPP) {
		a = RV(a); b = RV(b);
	}
	if (a == b) return 0;
	if (got[a][b] == -1) {
		got[a][b] = got[b][a] = getDistance(a,b);
	}
	assert(got[a][b] != -1);
	return got[a][b];
}

void run(vector<int> stuff, int A, int C, int location[], int stype[]) {
	vector<int> Ds;
	Ds.pb(C);

	sort(ALL(stuff), [&](int x, int y) {return dis(A,x) < dis(A,y);});

	for (int x : stuff) {
		int dstdf = dis(A,Ds.back()) + dis(Ds.back(), x) - dis(A,x);
		assert(dstdf % 2 == 0); dstdf /= 2;
		bool done = 0;
		for (int e : Ds) {
			if (location[Ds.back()] - location[e] == dstdf) {
				location[x] = location[e] - (dis(A,x) - dis(A,e));
				stype[x] = 1;
				bug(x, e, location[x]);
				done = 1; break;
			}
		}
		if (!done) {
			stype[x] = 2;
			location[x] = dis(A,x) + location[A];
			bug(x, "D", location[x]);
			Ds.pb(x);
		}
	}
}


void findLocation(int _n, int _first, int location[], int stype[])
{

	// add _first at the very end

	n = _n;
	memset(got, -1, sizeof got);
	fill(stype, stype+n, 0);
	// DO NOT CALL getDistance

	int A = 0, C = -1;

	REP(i,n) {
		if (i == A) continue;
		if (C == -1 || dis(A,i) < dis(A,C)) {
			C = i;
		}
	}
	assert(C != -1);

	vector<int> L, R; // to the left of A or to the right of C

	bug(A,C);


	REP(i,n) {
		if (i == A) {
			location[i] = 0; stype[i] = 1; // 1 is type C 
			continue;
		}
		if (i == C) {
			location[i] = 0 + dis(A,C); stype[i] = 2; // 2 is type D 
			continue;
		}
		if (dis(A,i) == dis(A,C) + dis(C,i)) {
			// to the left of C
			if (dis(C,i) < dis(A,C)) {
				// between A and C
				location[i] = dis(A,C) - dis(C,i);
				stype[i] = 1;
				bug(i, location[i], "btw A and C");
				continue;
			}else{
				L.pb(i);
			}
		}else{
			R.pb(i);
		}
	}

	run(R, A, C, location, stype);

	// reversal time (!?)

	REP(i,n) {
		location[i] = -location[i];
		if (stype[i]) stype[i] ^= 3;
	}

	run(L,C,A,location, stype);

	REP(i,n) {
		location[i] = -location[i];
		if (stype[i]) stype[i] ^= 3;
	}

	REP(i,n) {
		location[i] += _first;
		bug(i, stype[i]==1?"C":"D",location[i]);
	}
}	


/*
3
9
1 0
1 2
2 4
2 12
2 10
1 11
1 -10
2 -9
2 -7

*/

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