oj.uz

답안 #83464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83464 2018-11-08T04:19:23 Z qkxwsm 철로 (IOI14_rail) C++14
100 / 100
 134 ms 32124 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 5013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, P, A = -1, D = INF;
int dist[MAXN][MAXN];

int query(int x, int y)
{
	if (x > y) swap(x, y);
	return (x == y ? 0 : (dist[x][y] ? dist[x][y] : dist[x][y] = getDistance(x, y)));
}
bool cmp(int a, int b)
{
	return query(A, a) < query(A, b);
}

void findLocation(int n, int first, int location[], int stype[])
{
	N = n;
	//let's say we know all the answers to 0
	stype[0] = 1;
	location[0] = first;
	if (N == 1)
	{
		return;
	}
	for (int i = 0; i < N; i++)
	{
		if (i == 0) continue;
		int cur = query(0, i);
		if (cur < D)
		{
			A = i;
			D = cur;
		}
	}
	stype[A] = 2;
	location[A] = location[0] + D;
	vector<int> lt, rt; set<int> pos;
	for (int i = 0; i < N; i++)
	{
		if (i == 0 || i == A) continue;
		if (query(0, i) == query(0, A) + query(A, i))
		{
			if (query(A, i) <= query(A, 0))
			{
				stype[i] = 1;
				location[i] = location[A] - query(A, i);
			}
			else
			{
				lt.PB(i);
			}
		}
		else
		{
			rt.PB(i);
		}
	}
	sort(lt.begin(), lt.end(), cmp);
	int guy = 0;
	pos.insert(location[0]);
	for (int idx : lt)
	{
		// cerr << ' ' << idx << endl;
		int loc = location[guy] + query(guy, idx);
		int go = *(prev(pos.upper_bound(loc)));
		if (location[A] - go + loc - go == query(A, idx))
		{
			stype[idx] = 2;
			location[idx] = loc;
		}
		else
		{
			stype[idx] = 1;
			location[idx] = location[A] - query(A, idx);
			pos.insert(location[idx]);
			guy = idx;
		}
	}
	pos.clear();
	sort(rt.begin(), rt.end(), cmp);
	guy = A;
	pos.insert(location[A]);
	for (int idx : rt)
	{
		int loc = location[guy] - query(guy, idx);
		int go = *(pos.upper_bound(loc));
		if (go - location[0] + go - loc == query(0, idx))
		{
			stype[idx] = 1;
			location[idx] = loc;
		}
		else
		{
			stype[idx] = 2;
			location[idx] = location[0] + query(0, idx);
			pos.insert(location[idx]);
			guy = idx;
		}
	}
	// for (int i = 0; i < N; i++)
	// {
	// 	cerr << stype[i] << ' ' << location[i] << endl;
	// }
	//for a given 0: you can find the next 1
	//1 for type C, 2 for type D, 0 for nothing!
}
/*
4 6
1 16
1 1
1 3
2 5
1 14
2 22
*/
/*
4 6
1 3
1 1
2 5
1 16
1 14
2 22
*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 3 ms 800 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 880 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 20220 KB Output is correct
2 Correct 107 ms 20220 KB Output is correct
3 Correct 109 ms 22752 KB Output is correct
4 Correct 108 ms 22752 KB Output is correct
5 Correct 107 ms 22752 KB Output is correct
6 Correct 111 ms 24320 KB Output is correct
7 Correct 119 ms 28640 KB Output is correct
8 Correct 117 ms 30460 KB Output is correct
9 Correct 114 ms 30460 KB Output is correct
10 Correct 120 ms 32124 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 32124 KB Output is correct
2 Correct 105 ms 32124 KB Output is correct
3 Correct 107 ms 32124 KB Output is correct
4 Correct 108 ms 32124 KB Output is correct
5 Correct 112 ms 32124 KB Output is correct
6 Correct 112 ms 32124 KB Output is correct
7 Correct 118 ms 32124 KB Output is correct
8 Correct 133 ms 32124 KB Output is correct
9 Correct 105 ms 32124 KB Output is correct
10 Correct 126 ms 32124 KB Output is correct
11 Correct 118 ms 32124 KB Output is correct
12 Correct 134 ms 32124 KB Output is correct
13 Correct 116 ms 32124 KB Output is correct
14 Correct 111 ms 32124 KB Output is correct
15 Correct 113 ms 32124 KB Output is correct
16 Correct 111 ms 32124 KB Output is correct
17 Correct 109 ms 32124 KB Output is correct
18 Correct 118 ms 32124 KB Output is correct
19 Correct 117 ms 32124 KB Output is correct
20 Correct 111 ms 32124 KB Output is correct