oj.uz

답안 #547011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547011 2022-04-09T07:34:14 Z blue 철로 (IOI14_rail) C++17
100 / 100
 71 ms 844 KB 
#include "rail.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

using vi = vector<int>;

const int mx = 5'000;

int X;
vi dist0(mx);
vi distX(mx);

const int typeC = 1;
const int typeD = 2;

void findLocation(int N, int first, int location[], int stype[])
{
	dist0[0] = 0;
	for(int i = 1; i < N; i++)
	{
		dist0[i] = getDistance(0, i);
	}

	int lst[N];
	for(int i = 0; i < N; i++)
		lst[i] = i;

	sort(lst, lst+N, [] (int u, int v)
	{
		return dist0[u] < dist0[v];
	});

	X = lst[1];

	location[0] = first;
	stype[0] = typeC;

	location[X] = first + dist0[X];
	stype[X] = typeD;

	int L = 0;
	int R = X;


	for(int i = 0; i < N; i++)
	{
		if(i == 0) distX[0] = dist0[X];
		else if(i == X) distX[X] = 0;
		else distX[i] = getDistance(X, i);
	}

	set<int> Cs;
	set<int> Ds;

	Cs.insert(location[0]);
	Ds.insert(location[X]);

	// cerr << location[0] << ' ' << location[X] << '\n';

	for(int v = 2; v < N; v++)
	{
		int Q = lst[v];
		// cerr << "computing : " << Q << '\n';

		if(dist0[Q] != dist0[X] + distX[Q])
		{
			// cerr << "case 1\n";
			int drq = getDistance(R, Q);

			int d = dist0[R] + drq - dist0[Q];

			// cerr << "drq = " << drq << '\n';

			if(Ds.find(location[R] - d/2) != Ds.end())
			{
				location[Q] = location[R] - drq;
				stype[Q] = typeC;
			}
			else
			{
				location[Q] = location[0] + dist0[Q];
				stype[Q] = typeD;
			}
		}
		else if(distX[Q] != distX[0] + dist0[Q])
		{
			// cerr << "case 2\n";
			int dlq = getDistance(L, Q);

			int d = distX[L] + dlq - distX[Q];

			if(Cs.find(location[L] + d/2) != Cs.end())
			{
				location[Q] = location[L] + dlq;
				stype[Q] = typeD;
			}
			else
			{
				location[Q] = location[X] - distX[Q];
				stype[Q] = typeC;
			}
		}
		else
		{
			stype[Q] = typeC;
			location[Q] = location[X] - distX[Q];
		}

		if(location[Q] < location[L])
			L = Q;
		if(location[Q] > location[R])
			R = Q;

		if(stype[Q] == typeC)
			Cs.insert(location[Q]);
		else 
			Ds.insert(location[Q]);
	}

	// cerr << "computed\n";
	// for(int i = 0; i < N; i++) cerr << stype[i] << ' ' << location[i] << '\n';
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 624 KB Output is correct
2 Correct 68 ms 800 KB Output is correct
3 Correct 67 ms 668 KB Output is correct
4 Correct 67 ms 728 KB Output is correct
5 Correct 68 ms 792 KB Output is correct
6 Correct 68 ms 676 KB Output is correct
7 Correct 70 ms 844 KB Output is correct
8 Correct 67 ms 672 KB Output is correct
9 Correct 67 ms 680 KB Output is correct
10 Correct 69 ms 812 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 760 KB Output is correct
2 Correct 70 ms 792 KB Output is correct
3 Correct 67 ms 676 KB Output is correct
4 Correct 67 ms 684 KB Output is correct
5 Correct 69 ms 684 KB Output is correct
6 Correct 67 ms 804 KB Output is correct
7 Correct 68 ms 684 KB Output is correct
8 Correct 67 ms 672 KB Output is correct
9 Correct 68 ms 688 KB Output is correct
10 Correct 68 ms 668 KB Output is correct
11 Correct 67 ms 676 KB Output is correct
12 Correct 66 ms 684 KB Output is correct
13 Correct 66 ms 704 KB Output is correct
14 Correct 71 ms 800 KB Output is correct
15 Correct 67 ms 672 KB Output is correct
16 Correct 68 ms 676 KB Output is correct
17 Correct 67 ms 684 KB Output is correct
18 Correct 67 ms 684 KB Output is correct
19 Correct 70 ms 684 KB Output is correct
20 Correct 68 ms 680 KB Output is correct