oj.uz

Submission #48592

# Submission time Handle Problem Language Result Execution time Memory
48592 2018-05-17T05:46:55 Z gs12117 Rail (IOI14_rail) C++11
100 / 100
 215 ms 972 KB 
#include<vector>
#include<algorithm>
#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());
	int pd = 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;
		for (int j = 0; j < n; j++) {
			if (vchk[j] == 1 && location[j] == y&&stype[j] == 1) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) {
			stype[x] = 2;
			location[x] = location[pd] + pr;
			vchk[x] = 1;
		}
		else {
			stype[x] = 1;
			location[x] = location[f] - pl - p;
			vchk[x] = 1;
			pd = 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;
		for (int j = 0; j < n; j++) {
			if (vchk[j] == 1 && location[j] == y&&stype[j] == 2) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) {
			stype[x] = 1;
			location[x] = location[pd] - pr;
			vchk[x] = 1;
		}
		else {
			stype[x] = 2;
			location[x] = location[g] + pl + p;
			vchk[x] = 1;
			pd = x;
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < l.size(); i++) {
                  ~~^~~~~~~~~~
rail.cpp:91: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 252 KB Output is correct
2 Correct 3 ms 420 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 2 ms 544 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 876 KB Output is correct
2 Correct 167 ms 884 KB Output is correct
3 Correct 151 ms 884 KB Output is correct
4 Correct 161 ms 884 KB Output is correct
5 Correct 143 ms 920 KB Output is correct
6 Correct 167 ms 928 KB Output is correct
7 Correct 148 ms 928 KB Output is correct
8 Correct 144 ms 928 KB Output is correct
9 Correct 152 ms 928 KB Output is correct
10 Correct 138 ms 928 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 928 KB Output is correct
2 Correct 170 ms 928 KB Output is correct
3 Correct 152 ms 928 KB Output is correct
4 Correct 215 ms 928 KB Output is correct
5 Correct 136 ms 932 KB Output is correct
6 Correct 136 ms 936 KB Output is correct
7 Correct 164 ms 936 KB Output is correct
8 Correct 148 ms 936 KB Output is correct
9 Correct 158 ms 936 KB Output is correct
10 Correct 148 ms 936 KB Output is correct
11 Correct 155 ms 972 KB Output is correct
12 Correct 150 ms 972 KB Output is correct
13 Correct 159 ms 972 KB Output is correct
14 Correct 167 ms 972 KB Output is correct
15 Correct 147 ms 972 KB Output is correct
16 Correct 154 ms 972 KB Output is correct
17 Correct 146 ms 972 KB Output is correct
18 Correct 158 ms 972 KB Output is correct
19 Correct 144 ms 972 KB Output is correct
20 Correct 139 ms 972 KB Output is correct