oj.uz

Submission #8576

# Submission time Handle Problem Language Result Execution time Memory
8576 2014-09-17T10:50:46 Z cki86201 Rail (IOI14_rail) C++
30 / 100
 93 ms 828 KB 
#include "rail.h"
#include<algorithm>
using namespace std;

typedef pair<int,int> Pi;
#define X first
#define Y second

int F[5050], T[5050];
Pi tF[5050], tT[5050];
int tf, tt;
int st[5050], top;
int val[5050];

void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first, stype[0] = 1;
	int i, tar = 1;
	for(i=1;i<N;i++){
		F[i] = getDistance(0, i);
		if(F[tar] > F[i])tar = i;
	}
	location[tar] = F[tar] + first;
	stype[tar] = 2;
	for(i=1;i<N;i++)if(i != tar)T[i] = getDistance(tar, i);
	for(i=1;i<N;i++){
		if(i == tar)continue;
		if(F[i] == T[i] + F[tar])tT[tt++] = Pi(T[i], i);
		else tF[tf++] = Pi(F[i] - F[tar], i);
	}
	sort(tT, tT+tt);
	sort(tF, tF+tf);
	if(tt)val[tT[0].Y] = tT[0].X, stype[tT[0].Y] = 1;
	st[top++] = tT[0].Y;
	for(i=1;i<tt;i++){
		int t = getDistance(tT[i].Y, st[top-1]), j;
		for(j=0;j<top;j++){
			int b = val[st[j]]*2 - tT[i].X;
			if(val[st[j]]-b == t)break;
		}
		if(j == top){
			val[tT[i].Y] = tT[i].X, stype[tT[i].Y] = 1;
			st[top++] = tT[i].Y;
		}
		else{
			val[tT[i].Y] = val[st[j]]*2 - tT[i].X, stype[tT[i].Y] = 2;
		}
	}
	for(i=0;i<tt;i++)location[tT[i].Y] = location[tar] - val[tT[i].Y];

	top = 0;
	if(tf)val[tF[0].Y] = tF[0].X, stype[tF[0].Y] = 2;
	st[top++] = tF[0].Y;
	for(i=1;i<tf;i++){
		int t = getDistance(tF[i].Y, st[top-1]), j;
		for(j=0;j<top;j++){
			int b = val[st[j]]*2 - tF[i].X;
			if(val[st[j]]-b == t)break;
		}
		if(j == top){
			val[tF[i].Y] = tF[i].X, stype[tF[i].Y] = 2;
			st[top++] = tF[i].Y;
		}
		else{
			val[tF[i].Y] = val[st[j]]*2 - tF[i].X, stype[tF[i].Y] = 1;
		}
	}
	for(i=0;i<tf;i++)location[tF[i].Y] = location[tar] + val[tF[i].Y];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 712 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 712 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 828 KB Output isn't correct
2 Halted 0 ms 0 KB -