oj.uz

Submission #622552

# Submission time Handle Problem Language Result Execution time Memory
622552 2022-08-04T11:24:34 Z balbit Rail (IOI14_rail) C++14
100 / 100
 127 ms 98688 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98380 KB Output is correct
2 Correct 42 ms 98380 KB Output is correct
3 Correct 36 ms 98424 KB Output is correct
4 Correct 37 ms 98380 KB Output is correct
5 Correct 40 ms 98352 KB Output is correct
6 Correct 37 ms 98296 KB Output is correct
7 Correct 37 ms 98408 KB Output is correct
8 Correct 37 ms 98380 KB Output is correct
9 Correct 47 ms 98344 KB Output is correct
10 Correct 46 ms 98360 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98380 KB Output is correct
2 Correct 45 ms 98372 KB Output is correct
3 Correct 38 ms 98340 KB Output is correct
4 Correct 43 ms 98380 KB Output is correct
5 Correct 38 ms 98424 KB Output is correct
6 Correct 41 ms 98344 KB Output is correct
7 Correct 38 ms 98404 KB Output is correct
8 Correct 46 ms 98416 KB Output is correct
9 Correct 40 ms 98360 KB Output is correct
10 Correct 48 ms 98400 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 98496 KB Output is correct
2 Correct 112 ms 98556 KB Output is correct
3 Correct 104 ms 98556 KB Output is correct
4 Correct 114 ms 98604 KB Output is correct
5 Correct 105 ms 98548 KB Output is correct
6 Correct 109 ms 98508 KB Output is correct
7 Correct 111 ms 98596 KB Output is correct
8 Correct 104 ms 98564 KB Output is correct
9 Correct 127 ms 98508 KB Output is correct
10 Correct 107 ms 98552 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 98504 KB Output is correct
2 Correct 108 ms 98592 KB Output is correct
3 Correct 112 ms 98548 KB Output is correct
4 Correct 104 ms 98564 KB Output is correct
5 Correct 107 ms 98560 KB Output is correct
6 Correct 109 ms 98688 KB Output is correct
7 Correct 106 ms 98552 KB Output is correct
8 Correct 115 ms 98580 KB Output is correct
9 Correct 110 ms 98608 KB Output is correct
10 Correct 105 ms 98596 KB Output is correct
11 Correct 111 ms 98556 KB Output is correct
12 Correct 112 ms 98560 KB Output is correct
13 Correct 115 ms 98508 KB Output is correct
14 Correct 109 ms 98636 KB Output is correct
15 Correct 105 ms 98564 KB Output is correct
16 Correct 110 ms 98508 KB Output is correct
17 Correct 113 ms 98508 KB Output is correct
18 Correct 110 ms 98568 KB Output is correct
19 Correct 106 ms 98608 KB Output is correct
20 Correct 105 ms 98552 KB Output is correct