oj.uz

Submission #48593

# Submission time Handle Problem Language Result Execution time Memory
48593 2018-05-17T05:51:39 Z gs12117 Rail (IOI14_rail) C++11
100 / 100
 186 ms 1100 KB 
#include<vector>
#include<algorithm>
#include<map>
#include "rail.h"
int n;
int distz[5010];
int distf[5010];
int side[5010];
int vchk[5010];
struct stn {
	int loc, val;
	bool operator<(const stn&r)const {
		return val < r.val;
	}
};
void findLocation(int N, int first, int location[], int stype[])
{
	if (n == 1) {
		location[0] = first;
		stype[0] = 1;
		return;
	}
	n = N;
	distz[0] = 0;
	int f = -1;
	for (int i = 1; i < n; i++) {
		distz[i] = getDistance(0, i);
		if (f == -1 || distz[i] < distz[f])f = i;
	}
	int rdf = distz[f];
	distf[f] = 0;
	distf[0] = rdf;
	int g = 0;
	for (int i = 1; i < n; i++) {
		if (i == f)continue;
		distf[i] = getDistance(i, f);
		if (distz[i] == distf[i] + rdf)side[i] = 1;
		else side[i] = 0;
		if (distf[i] < distf[g])g = i;
	}
	side[0] = 1;
	int df = distf[g];
	location[f] = first + rdf;
	location[g] = location[f] - df;
	stype[f] = 2;
	stype[g] = 1;
	for (int i = 0; i < n; i++) {
		vchk[i] = 0;
	}
	vchk[f] = 1;
	vchk[g] = 1;
	std::vector<stn> l, r;
	for (int i = 0; i < n; i++) {
		if (i == f || i == g)continue;
		stn t;
		t.loc = i;
		t.val = distf[i];
		if (side[i] == 1)l.push_back(t);
		else r.push_back(t);
	}
	std::sort(l.begin(), l.end());
	std::sort(r.begin(), r.end());
	std::map<int,int> m;
	int pd = g;
	m[location[f]] = stype[f];
	m[location[g]] = stype[g];
	for (int i = 0; i < l.size(); i++) {
		int x = l[i].loc;
		int d = l[i].val;
		int pr = getDistance(pd, x);
		int pl = location[f] - location[pd];
		int p = d - pl;
		int q = (pr - p) / 2;
		int y = location[f] - (pl - q);
		int flag = 0;
		if (m[y] == 1)flag = 1;
		if (flag == 1) {
			stype[x] = 2;
			location[x] = location[pd] + pr;
			vchk[x] = 1;
			m[location[x]] = stype[x];
		}
		else {
			stype[x] = 1;
			location[x] = location[f] - pl - p;
			vchk[x] = 1;
			pd = x;
			m[location[x]] = stype[x];
		}
	}
	pd = f;
	for (int i = 0; i < r.size(); i++) {
		int x = r[i].loc;
		int d = r[i].val;
		int pr = getDistance(pd, x);
		int pl = location[pd] - location[g];
		int p = d - df - pl;
		int q = (pr - p) / 2;
		int y = location[g] + (pl - q);
		int flag = 0;
		if (m[y] == 2)flag = 1;
		if (flag == 1) {
			stype[x] = 1;
			location[x] = location[pd] - pr;
			vchk[x] = 1;
			m[location[x]] = stype[x];
		}
		else {
			stype[x] = 2;
			location[x] = location[g] + pl + p;
			vchk[x] = 1;
			pd = x;
			m[location[x]] = stype[x];
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < l.size(); i++) {
                  ~~^~~~~~~~~~
rail.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < r.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 396 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 3 ms 472 KB Output is correct
7 Correct 2 ms 472 KB Output is correct
8 Correct 2 ms 472 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 3 ms 520 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 520 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 612 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 3 ms 732 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 732 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1072 KB Output is correct
2 Correct 89 ms 1072 KB Output is correct
3 Correct 85 ms 1072 KB Output is correct
4 Correct 95 ms 1072 KB Output is correct
5 Correct 87 ms 1072 KB Output is correct
6 Correct 89 ms 1080 KB Output is correct
7 Correct 114 ms 1080 KB Output is correct
8 Correct 93 ms 1080 KB Output is correct
9 Correct 94 ms 1080 KB Output is correct
10 Correct 88 ms 1080 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1080 KB Output is correct
2 Correct 86 ms 1080 KB Output is correct
3 Correct 85 ms 1080 KB Output is correct
4 Correct 92 ms 1080 KB Output is correct
5 Correct 112 ms 1080 KB Output is correct
6 Correct 93 ms 1080 KB Output is correct
7 Correct 107 ms 1080 KB Output is correct
8 Correct 186 ms 1080 KB Output is correct
9 Correct 129 ms 1080 KB Output is correct
10 Correct 96 ms 1080 KB Output is correct
11 Correct 92 ms 1080 KB Output is correct
12 Correct 94 ms 1080 KB Output is correct
13 Correct 96 ms 1080 KB Output is correct
14 Correct 94 ms 1080 KB Output is correct
15 Correct 93 ms 1084 KB Output is correct
16 Correct 93 ms 1100 KB Output is correct
17 Correct 95 ms 1100 KB Output is correct
18 Correct 99 ms 1100 KB Output is correct
19 Correct 103 ms 1100 KB Output is correct
20 Correct 93 ms 1100 KB Output is correct