oj.uz

Submission #496950

# Submission time Handle Problem Language Result Execution time Memory
496950 2021-12-22T07:27:52 Z Temmie Rail (IOI14_rail) C++17
100 / 100
 84 ms 16120 KB 
#include "rail.h"
#include <bits/stdc++.h>

//int getDistance(int i, int j) {
	//return 0;
//}

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	std::vector <int> inv(int(4e6) + 3, -1);
	inv[first] = 0;
	if (n == 1) {
		return;
	}
	std::vector <std::pair <int, int>> a(n - 1);
	for (int i = 1; i < n; i++) {
		a[i - 1] = { getDistance(0, i), i };
	}
	std::sort(a.rbegin(), a.rend());
	int l = 0, r = a.back().second;
	location[r] = first + a.back().first;
	stype[r] = 2;
	inv[location[r]] = r;
	a.pop_back();
	while (a.size()) {
		int ind = a.back().second;
		a.pop_back();
		int left = getDistance(l, ind);
		int right = getDistance(r, ind);
		int loc1 = location[l] + left;
		int loc2 = location[r] - right;
		int mid = (loc1 + loc2) >> 1;
		if (inv[mid] != -1) {
			stype[ind] = stype[inv[mid]] == 1 ? 2 : 1;
		} else if (first < mid) {
			stype[ind] = 2;
		} else {
			stype[ind] = 1;
		}
		if (stype[ind] == 1) {
			std::swap(loc1, loc2);
		}
		location[ind] = loc1;
		inv[location[ind]] = ind;
		if (loc1 > location[r]) {
			r = ind;
		} else if (loc1 < location[l]) {
			l = ind;
		}
	}
}

//int main() {
	
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 8 ms 15984 KB Output is correct
3 Correct 6 ms 15976 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 7 ms 15948 KB Output is correct
7 Correct 7 ms 15948 KB Output is correct
8 Correct 7 ms 15948 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 7 ms 15980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 6 ms 15996 KB Output is correct
3 Correct 7 ms 15924 KB Output is correct
4 Correct 7 ms 15948 KB Output is correct
5 Correct 8 ms 15948 KB Output is correct
6 Correct 7 ms 15992 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 8 ms 15948 KB Output is correct
9 Correct 9 ms 15992 KB Output is correct
10 Correct 8 ms 15988 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16064 KB Output is correct
2 Correct 79 ms 16096 KB Output is correct
3 Correct 73 ms 16064 KB Output is correct
4 Correct 72 ms 16064 KB Output is correct
5 Correct 71 ms 16116 KB Output is correct
6 Correct 73 ms 16076 KB Output is correct
7 Correct 73 ms 16120 KB Output is correct
8 Correct 81 ms 16080 KB Output is correct
9 Correct 76 ms 16076 KB Output is correct
10 Correct 78 ms 16064 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16076 KB Output is correct
2 Correct 77 ms 16076 KB Output is correct
3 Correct 78 ms 16064 KB Output is correct
4 Correct 72 ms 16072 KB Output is correct
5 Correct 72 ms 16064 KB Output is correct
6 Correct 84 ms 16060 KB Output is correct
7 Correct 82 ms 16060 KB Output is correct
8 Correct 74 ms 16064 KB Output is correct
9 Correct 72 ms 16060 KB Output is correct
10 Correct 74 ms 16064 KB Output is correct
11 Correct 78 ms 16060 KB Output is correct
12 Correct 74 ms 16076 KB Output is correct
13 Correct 82 ms 16068 KB Output is correct
14 Correct 72 ms 16080 KB Output is correct
15 Correct 71 ms 16096 KB Output is correct
16 Correct 80 ms 16068 KB Output is correct
17 Correct 83 ms 16076 KB Output is correct
18 Correct 75 ms 16068 KB Output is correct
19 Correct 82 ms 16076 KB Output is correct
20 Correct 82 ms 16108 KB Output is correct