oj.uz

Submission #38853

# Submission time Handle Problem Language Result Execution time Memory
38853 2018-01-07T10:10:00 Z 14kg Rail (IOI14_rail) C++11
100 / 100
 127 ms 848 KB 
#include "rail.h"
#include <stdio.h>
#include <algorithm>
#define N 5001
#define INF 999999999

using namespace std;
int n, zd[N], zero;
int rd[N], rw, r_num, lw, l_num;
int L_len, R_len, S_len, S[N];
pair<int, int> L[N], R[N];

void findLocation(int _n, int _zero, int out1[], int out2[]) {
	int temp = INF, len;
	bool check;
	n = _n, zero = _zero;

	for (int i = 1; i < n; i++) {
		zd[i] = getDistance(0, i);
		if (temp > zd[i]) {
			temp = zd[i], r_num = i;
			rw = zero + temp;
		}
	}

	temp = rw - zero, lw = zero;
	for (int i = 1; i < n; i++)
	if (i != r_num) {
		rd[i] = getDistance(r_num, i);
		if (temp > rd[i])
			temp = rd[i], lw = rw - rd[i], l_num = i;
	}

	out1[0] = zero, out2[0] = 1;
	out1[r_num] = rw, out2[r_num] = 2;
	out1[l_num] = lw, out2[l_num] = 1;
	for (int i = 1; i < n; i++)
		if (i != r_num && i != l_num) {
			if (rd[i] - (rw - lw) == zd[i] - (lw - zero)) {
				out1[i] = zero + zd[i], out2[i] = 2;
				R[++R_len] = { out1[i],i };
			}
			else if (rd[i] + rw - zero == zd[i]) {
				out1[i] = rw - rd[i], out2[i] = 1;
				L[++L_len] = { -out1[i],i };
			}
			// printf("%d/%d) %d %d\n", i, lw, rd[i] - (rw - lw), zd[i] - (lw - zero));
		}

	L[++L_len] = { -zero,0 };
	sort(L + 1, L + L_len + 1), sort(R + 1, R + R_len + 1);
	
	temp = r_num, S[S_len = 1] = r_num;
	for (int i = 1; i <= R_len; i++) {
		len = getDistance(temp, R[i].second), check = true;

		for (int j = S_len; j >= 1 && check; j--)
			if (zd[R[i].second] == zd[temp] + len - (out1[temp] - S[j]) * 2)
				out1[R[i].second] = out1[temp] - len, out2[R[i].second] = 1, check = false;
		if (check) temp = R[i].second, S[++S_len] = out1[temp];
	}

	temp = l_num, S[S_len = 1] = l_num;
	for (int i = 1; i <= L_len; i++) {
		len = getDistance(temp, L[i].second), check = true;

		for (int j = S_len; j >= 1 && check; j--)
			if (rd[L[i].second] == rd[temp] + len - (S[j] - out1[temp]) * 2)
				out1[L[i].second] = out1[temp] + len, out2[L[i].second] = 2, check = false;

		if (check) temp = L[i].second, S[++S_len] = out1[temp];
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 748 KB Output is correct
2 Correct 93 ms 828 KB Output is correct
3 Correct 111 ms 828 KB Output is correct
4 Correct 96 ms 828 KB Output is correct
5 Correct 127 ms 828 KB Output is correct
6 Correct 96 ms 828 KB Output is correct
7 Correct 92 ms 828 KB Output is correct
8 Correct 100 ms 828 KB Output is correct
9 Correct 97 ms 832 KB Output is correct
10 Correct 92 ms 832 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 832 KB Output is correct
2 Correct 94 ms 832 KB Output is correct
3 Correct 96 ms 832 KB Output is correct
4 Correct 101 ms 832 KB Output is correct
5 Correct 109 ms 836 KB Output is correct
6 Correct 116 ms 836 KB Output is correct
7 Correct 91 ms 836 KB Output is correct
8 Correct 90 ms 836 KB Output is correct
9 Correct 95 ms 836 KB Output is correct
10 Correct 93 ms 848 KB Output is correct
11 Correct 105 ms 848 KB Output is correct
12 Correct 96 ms 848 KB Output is correct
13 Correct 93 ms 848 KB Output is correct
14 Correct 97 ms 848 KB Output is correct
15 Correct 96 ms 848 KB Output is correct
16 Correct 106 ms 848 KB Output is correct
17 Correct 106 ms 848 KB Output is correct
18 Correct 95 ms 848 KB Output is correct
19 Correct 125 ms 848 KB Output is correct
20 Correct 94 ms 848 KB Output is correct