oj.uz

답안 #57968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57968 2018-07-16T14:53:17 Z aome 철로 (IOI14_rail) C++17
100 / 100
 122 ms 1712 KB 
#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

int dis[2][N];

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	for (int i = 1; i < n; ++i) {
		dis[0][i] = getDistance(0, i);
	}
	int p1 = 1;
	for (int i = 2; i < n; ++i) {
		if (dis[0][p1] > dis[0][i]) p1 = i;
	}
	location[p1] = location[0] + dis[0][p1], stype[p1] = 2;
	vector<int> vecl, vecr;
	// cout << "#p1 " << p1 << '\n';
	for (int i = 1; i < n; ++i) {
		if (i == p1) continue;
		dis[1][i] = getDistance(p1, i);
		// cout << "#dis1 " << i << ' ' << dis[1][i] << '\n';
		if (dis[0][i] == dis[0][p1] + dis[1][i] && dis[1][i] <= dis[0][p1]) {
			location[i] = location[p1] - dis[1][i], stype[i] = 1;
			// cout << "ax " << i << '\n';
		}
		else {
			if (dis[1][i] + dis[0][p1] == dis[0][i]) vecl.push_back(i);
			else vecr.push_back(i);
		}
	}
	sort(vecl.begin(), vecl.end(), [&] (int x, int y) {
		return dis[1][x] < dis[1][y];
	});
	sort(vecr.begin(), vecr.end(), [&] (int x, int y) {
		return dis[0][x] < dis[0][y];
	});
	// for (auto i : vecl) cout << i << ' '; cout << '\n';
	// for (auto i : vecr) cout << i << ' '; cout << '\n';
	int cur;
	vector<int> vec;
	{	
		cur = p1;
		vec.clear();
		vec.push_back(p1);
		for (auto i : vecr) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = dis[0][i] + location[0];
			int tmp3 = location[cur] - tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] >= tmp3) { p = j; break; }
			}
			// cout << "#at " << i << '\n';
			// cout << cur << ' ' << tmp1 << '\n';
			// cout << tmp2 << ' ' << location[p] << ' ' << tmp3 << '\n';
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 1;
			}
			else {
				location[i] = tmp2, stype[i] = 2, cur = i, vec.push_back(i);
			}
		}
	}
	{
		cur = 0;
		vec.clear();
		vec.push_back(0);
		for (auto i : vecl) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = location[p1] - dis[1][i];
			int tmp3 = location[cur] + tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] <= tmp3) { p = j; break; }
			}
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 2;
			}
			else {
				location[i] = tmp2, stype[i] = 1, cur = i, vec.push_back(i);
			}
		}
	}
	// for (int i = 0; i < n; ++i) {
		// cout << location[i] << ' ' << (stype[i] == 1 ? '(' : ')') << '\n';
	// }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 3 ms 496 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 2 ms 544 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 744 KB Output is correct
2 Correct 98 ms 784 KB Output is correct
3 Correct 93 ms 944 KB Output is correct
4 Correct 108 ms 944 KB Output is correct
5 Correct 101 ms 944 KB Output is correct
6 Correct 102 ms 944 KB Output is correct
7 Correct 107 ms 944 KB Output is correct
8 Correct 88 ms 944 KB Output is correct
9 Correct 100 ms 944 KB Output is correct
10 Correct 122 ms 1108 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 1108 KB Output is correct
2 Correct 93 ms 1108 KB Output is correct
3 Correct 94 ms 1108 KB Output is correct
4 Correct 92 ms 1108 KB Output is correct
5 Correct 89 ms 1112 KB Output is correct
6 Correct 93 ms 1112 KB Output is correct
7 Correct 92 ms 1112 KB Output is correct
8 Correct 85 ms 1232 KB Output is correct
9 Correct 103 ms 1232 KB Output is correct
10 Correct 102 ms 1384 KB Output is correct
11 Correct 93 ms 1384 KB Output is correct
12 Correct 108 ms 1384 KB Output is correct
13 Correct 89 ms 1404 KB Output is correct
14 Correct 98 ms 1448 KB Output is correct
15 Correct 90 ms 1492 KB Output is correct
16 Correct 92 ms 1536 KB Output is correct
17 Correct 108 ms 1588 KB Output is correct
18 Correct 97 ms 1588 KB Output is correct
19 Correct 90 ms 1588 KB Output is correct
20 Correct 93 ms 1712 KB Output is correct