oj.uz

Submission #38852

# Submission time Handle Problem Language Result Execution time Memory
38852 2018-01-07T10:08:56 Z 14kg Rail (IOI14_rail) C++11
30 / 100
 97 ms 832 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;
		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;
		// printf("> %d   /%d %d\n", L[i].second, rd[L[i].second], rd[temp] + len);
		for (int j = S_len; j >= 1 && check; j--)
		//	printf("%d %d\n", rd[L[i].second], rd[temp] + len - (S[i] - out1[temp]) * 2);
			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 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 608 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 832 KB Output isn't correct
2 Halted 0 ms 0 KB -