oj.uz

Submission #838286

# Submission time Handle Problem Language Result Execution time Memory
838286 2023-08-26T12:54:24 Z pavement Rail (IOI14_rail) C++17
100 / 100
 93 ms 98784 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

void findLocation(int N, int first, int location[], int stype[]) {
	vector<int> left, right;
	vector<vector<int> > dist(N, vector<int>(N));
	location[0] = first;
	stype[0] = 1;
	dist[0][0] = 0;
	for (int i = 1; i < N; i++) {
		dist[0][i] = getDistance(0, i);
	}
	int X = min_element(dist[0].begin() + 1, dist[0].end()) - dist[0].begin(), Y = 0;
	stype[X] = 2;
	location[X] = first + dist[0][X];
	for (int i = 0; i < N; i++) {
		if (i == 0 || i == X) {
			continue;
		}
		dist[X][i] = getDistance(X, i);
		if (dist[0][X] + dist[X][i] == dist[0][i] && dist[X][i] < dist[0][X]) {
			stype[i] = 1;
			location[i] = location[X] - dist[X][i];
			if (location[Y] < location[i]) {
				Y = i;
			}
		} else if (dist[0][X] + dist[X][i] == dist[0][i]) {
			// left side
			left.pb(i);
		} else {
			// right side
			right.pb(i);
		}
	}
	// handle left side
	if (!left.empty()) {
		map<int, int> processed;
		sort(left.begin(), left.end(), [&](const int &lhs, const int &rhs) {
			return dist[X][lhs] < dist[X][rhs];
		});
		int cl = left[0];
		location[cl] = location[X] - dist[X][cl];
		stype[cl] = 1;
		processed[location[cl]] = stype[cl];
		for (int i = 1; i < (int)left.size(); i++) {
			int cur = left[i];
			int tmp = getDistance(cl, cur);
			int v = dist[X][cl] + tmp - dist[X][cur];
			assert(v % 2 == 0);
			if (processed.find(location[cl] + v / 2) == processed.end() || processed[location[cl] + v / 2] == 2) {
				location[cur] = location[cl] - (tmp - v);
				stype[cur] = 1;
				cl = cur;
			} else {
				location[cur] = location[cl] + tmp;
				stype[cur] = 2;
			}
			processed[location[cur]] = stype[cur];
		}
	}
	// handle right side
	if (!right.empty()) {
		for (int i : right) {
			dist[Y][i] = dist[0][i] - (location[Y] - location[0]);
		}
		map<int, int> processed;
		sort(right.begin(), right.end(), [&](const int &lhs, const int &rhs) {
			return dist[Y][lhs] < dist[Y][rhs];
		});
		int cl = right[0];
		location[cl] = location[Y] + dist[Y][cl];
		stype[cl] = 2;
		processed[location[cl]] = stype[cl];
		for (int i = 1; i < (int)right.size(); i++) {
			int cur = right[i];
			int tmp = getDistance(cl, cur);
			int v = dist[Y][cl] + tmp - dist[Y][cur];
			assert(v % 2 == 0);
			if (processed.find(location[cl] - v / 2) == processed.end() || processed[location[cl] - v / 2] == 1) {
				location[cur] = location[cl] + (tmp - v);
				stype[cur] = 2;
				cl = cur;
			} else {
				location[cur] = location[cl] - tmp;
				stype[cur] = 1;
			}
			processed[location[cur]] = stype[cur];
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 98632 KB Output is correct
2 Correct 93 ms 98684 KB Output is correct
3 Correct 85 ms 98636 KB Output is correct
4 Correct 87 ms 98680 KB Output is correct
5 Correct 91 ms 98676 KB Output is correct
6 Correct 87 ms 98784 KB Output is correct
7 Correct 86 ms 98680 KB Output is correct
8 Correct 90 ms 98656 KB Output is correct
9 Correct 87 ms 98700 KB Output is correct
10 Correct 84 ms 98612 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 98644 KB Output is correct
2 Correct 93 ms 98688 KB Output is correct
3 Correct 86 ms 98676 KB Output is correct
4 Correct 86 ms 98636 KB Output is correct
5 Correct 86 ms 98688 KB Output is correct
6 Correct 87 ms 98764 KB Output is correct
7 Correct 89 ms 98676 KB Output is correct
8 Correct 87 ms 98676 KB Output is correct
9 Correct 86 ms 98692 KB Output is correct
10 Correct 90 ms 98624 KB Output is correct
11 Correct 87 ms 98756 KB Output is correct
12 Correct 89 ms 98680 KB Output is correct
13 Correct 86 ms 98664 KB Output is correct
14 Correct 87 ms 98636 KB Output is correct
15 Correct 87 ms 98636 KB Output is correct
16 Correct 87 ms 98672 KB Output is correct
17 Correct 86 ms 98736 KB Output is correct
18 Correct 86 ms 98636 KB Output is correct
19 Correct 86 ms 98676 KB Output is correct
20 Correct 90 ms 98636 KB Output is correct