oj.uz

Submission #763379

# Submission time Handle Problem Language Result Execution time Memory
763379 2023-06-22T08:44:11 Z SanguineChameleon Rail (IOI14_rail) C++17
100 / 100
 91 ms 102708 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e3 + 20;
const int maxM = 1e6 + 20;
int *location;
int *stype;
int btype[maxM];
int memo[maxN][maxN];
int X, Y, L, R;

int dist(int u, int v) {
	if (memo[u][v] != -1) {
		return memo[u][v];
	}
	else {
		return memo[u][v] = memo[v][u] = getDistance(u, v);
	}
}

bool cmpX(int u, int v) {
	return dist(X, u) < dist(X, v);
}

bool cmpY(int u, int v) {
	return dist(Y, u) < dist(Y, v);
}

void answer(int id, int loc, int type) {
	location[id] = loc;
	stype[id] = type;
	btype[loc] = type;
}

void findLocation(int N, int first, int _location[], int _stype[]) {
	location = _location;
	stype = _stype;
	for (int i = 0; i < N; i++) {
		location[i] = -1;
		stype[i] = -1;
		for (int j = 0; j < N; j++) {
			memo[i][j] = -1;
		}
	}
	for (int i = 0; i < maxM; i++) {
		btype[i] = -1;
	}
	X = 0;
	answer(X, first, 1);
	Y = 1;
	for (int i = 0; i < N; i++) {
		if (i != X && dist(X, i) < dist(X, Y)) {
			Y = i;
		}
	}
	answer(Y, location[X] + dist(X, Y), 2);
	vector<int> left;
	vector<int> right;
	for (int i = 0; i < N; i++) {
		if (i == X || i == Y) {
			continue;
		}
		if (dist(X, i) == dist(X, Y) + dist(Y, i)) {
			if (dist(Y, i) < dist(Y, X)) {
				answer(i, location[Y] - dist(Y, i), 1);
			}
			else {
				left.push_back(i);
			}
		}
		else {
			right.push_back(i);
		}
	}
	sort(left.begin(), left.end(), cmpX);
	sort(right.begin(), right.end(), cmpY);
	L = X;
	R = Y;
	for (auto i: left) {
		int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
		if (btype[B] == 1) {
			int A = location[L] + dist(L, i);
			answer(i, A, 2);
		}
		else {
			int A = location[R] - dist(R, i);
			answer(i, A, 1);
			L = i;
		}
	}
	L = X;
	R = Y;
	for (auto i: right) {
		int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
		if (btype[B] == 2) {
			int A = location[R] - dist(R, i);
			answer(i, A, 1);
		}
		else {
			int A = location[L] + dist(L, i);
			answer(i, A, 2);
			R = i;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4692 KB Output is correct
2 Correct 2 ms 4732 KB Output is correct
3 Correct 2 ms 4692 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 2 ms 4736 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 2 ms 4736 KB Output is correct
9 Correct 2 ms 4732 KB Output is correct
10 Correct 2 ms 4692 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4644 KB Output is correct
2 Correct 2 ms 4692 KB Output is correct
3 Correct 2 ms 4740 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 2 ms 4692 KB Output is correct
9 Correct 2 ms 4692 KB Output is correct
10 Correct 3 ms 4736 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 102648 KB Output is correct
2 Correct 78 ms 102652 KB Output is correct
3 Correct 82 ms 102664 KB Output is correct
4 Correct 78 ms 102664 KB Output is correct
5 Correct 79 ms 102652 KB Output is correct
6 Correct 82 ms 102652 KB Output is correct
7 Correct 79 ms 102664 KB Output is correct
8 Correct 81 ms 102664 KB Output is correct
9 Correct 80 ms 102668 KB Output is correct
10 Correct 81 ms 102664 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 102668 KB Output is correct
2 Correct 81 ms 102664 KB Output is correct
3 Correct 80 ms 102708 KB Output is correct
4 Correct 80 ms 102680 KB Output is correct
5 Correct 80 ms 102660 KB Output is correct
6 Correct 91 ms 102652 KB Output is correct
7 Correct 84 ms 102592 KB Output is correct
8 Correct 79 ms 102668 KB Output is correct
9 Correct 78 ms 102652 KB Output is correct
10 Correct 79 ms 102652 KB Output is correct
11 Correct 78 ms 102664 KB Output is correct
12 Correct 79 ms 102668 KB Output is correct
13 Correct 80 ms 102652 KB Output is correct
14 Correct 91 ms 102652 KB Output is correct
15 Correct 79 ms 102692 KB Output is correct
16 Correct 79 ms 102580 KB Output is correct
17 Correct 81 ms 102624 KB Output is correct
18 Correct 79 ms 102656 KB Output is correct
19 Correct 79 ms 102660 KB Output is correct
20 Correct 79 ms 102664 KB Output is correct