oj.uz

Submission #652541

# Submission time Handle Problem Language Result Execution time Memory
652541 2022-10-22T21:32:13 Z ymm Rail (IOI14_rail) C++17
100 / 100
 74 ms 844 KB 
#include "rail.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 5010;
int from_0[N];
int from_1[N];
vector<pii> lefty;
vector<pii> wright;
int n;

enum {
	C = 1,
	D = 2,
};

map<int, int> mp;

void findLocation(int _N, int first, int location[], int stype[])
{
	n = _N;
	int mn = 1;
	Loop (i,1,n) {
		from_0[i] = getDistance(0, i);
		if (from_0[i] < from_0[mn])
			mn = i;
	}
	int X, Y = 1e9+10;
	Loop (i,0,n) {
		if (i == mn)
			continue;
		from_1[i] = getDistance(mn, i);
		if (from_1[i] < Y)
			Y = from_1[i];
	}
	X = from_0[mn] - Y;
	from_0[0] = 2*(X+Y);
	Loop (i,0,n) {
		if (i == mn)
			continue;
		if (from_0[i] - from_1[i] == X-Y)
			wright.push_back({from_1[i], i});
		else if (from_0[i] - from_1[i] == X+Y)
			lefty.push_back({from_1[i], i});
		else
			assert(false);
	}
	from_1[mn] = from_0[0];
	sort(lefty.begin(), lefty.end());
	sort(wright.begin(), wright.end());
	assert(lefty.size());
	int rD = mn, lC = lefty.front().second;
	lefty.erase(lefty.begin());
	location[mn] = first + from_0[mn];
	stype[mn] = D;
	mp[location[mn]] = D;
	location[lC] = location[mn] - from_1[lC];
	stype[lC] = C;
	mp[location[lC]] = C;
	for (auto [_, i] : wright) {
		int disr = getDistance(rD, i);
		int locD = first + from_0[i];
		int locC = location[rD] - disr;
		int locX = (locC + locD)/2;
		if (mp[locX] != D) {
			stype[i] = D;
			location[i] = locD;
			mp[location[i]] = D;
			rD = i;
		} else {
			stype[i] = C;
			location[i] = locC;
			mp[location[i]] = C;
		}
	}
	for (auto [_, i] : lefty) {
		int disl = getDistance(lC, i);
		int locC = location[mn] - from_1[i];
		int locD = location[lC] + disl;
		int locX = (locC + locD)/2;
		if (mp[locX] != C) {
			stype[i] = C;
			location[i] = locC;
			mp[location[i]] = C;
			lC = i;
		} else {
			stype[i] = D;
			location[i] = locD;
			mp[location[i]] = D;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 0 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 71 ms 708 KB Output is correct
2 Correct 68 ms 712 KB Output is correct
3 Correct 74 ms 716 KB Output is correct
4 Correct 72 ms 720 KB Output is correct
5 Correct 69 ms 728 KB Output is correct
6 Correct 73 ms 752 KB Output is correct
7 Correct 69 ms 764 KB Output is correct
8 Correct 69 ms 752 KB Output is correct
9 Correct 70 ms 760 KB Output is correct
10 Correct 68 ms 764 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 728 KB Output is correct
2 Correct 69 ms 720 KB Output is correct
3 Correct 71 ms 844 KB Output is correct
4 Correct 68 ms 712 KB Output is correct
5 Correct 67 ms 712 KB Output is correct
6 Correct 70 ms 720 KB Output is correct
7 Correct 68 ms 772 KB Output is correct
8 Correct 68 ms 760 KB Output is correct
9 Correct 69 ms 760 KB Output is correct
10 Correct 69 ms 760 KB Output is correct
11 Correct 68 ms 760 KB Output is correct
12 Correct 70 ms 776 KB Output is correct
13 Correct 71 ms 772 KB Output is correct
14 Correct 68 ms 776 KB Output is correct
15 Correct 69 ms 756 KB Output is correct
16 Correct 69 ms 760 KB Output is correct
17 Correct 69 ms 772 KB Output is correct
18 Correct 66 ms 768 KB Output is correct
19 Correct 68 ms 768 KB Output is correct
20 Correct 68 ms 768 KB Output is correct