oj.uz

Submission #64512

# Submission time Handle Problem Language Result Execution time Memory
64512 2018-08-04T17:22:40 Z TadijaSebez Rail (IOI14_rail) C++11
100 / 100
 160 ms 32252 KB 
#include "rail.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define pb push_back
const int N=5050;
int dist[N][N];
int Get(int i, int j)
{
	if(i>j) return Get(j,i);
	if(dist[i][j]) return dist[i][j];
	return dist[i][j]=getDistance(i,j);
}
map<int,int> dir;
int fir=1;
bool comp1(int i, int j){ return Get(0,i)<Get(0,j);}
bool comp2(int i, int j){ return Get(fir,i)<Get(fir,j);}
void findLocation(int n, int st, int d[], int t[])
{
	d[0]=st;
	t[0]=1;
	dir[d[0]]=t[0];
	if(n==1) return;
	int i,j;fir=1;
	vector<int> left,right;
	for(i=2;i<n;i++) if(Get(0,fir)>Get(0,i)) fir=i;
	d[fir]=st+Get(0,fir);
	t[fir]=2;
	dir[d[fir]]=t[fir];
	for(i=1;i<n;i++)
	{
		if(i==fir) continue;
		if(Get(0,i)==d[fir]-d[0]+Get(fir,i))
		{
			if(d[fir]-d[0]>Get(fir,i))
			{
				t[i]=1;
				d[i]=d[fir]-Get(fir,i);
				dir[d[i]]=t[i];
			}
			else left.pb(i);
		}
		else right.pb(i);
	}
	sort(left.begin(),left.end(),comp2);
	sort(right.begin(),right.end(),comp1);
	int l=0,r=fir;
	for(i=0;i<left.size();i++)
	{
		int x=left[i];
		int val=(d[r]-d[l]+Get(l,x)-Get(r,x))/2;
		if(dir[d[l]+val]==1)
		{
			d[x]=d[l]+Get(l,x);
			t[x]=2;
			dir[d[x]]=t[x];
		}
		else
		{
			d[x]=d[r]-Get(r,x);
			t[x]=1;
			dir[d[x]]=t[x];
			l=x;
		}
	}
	l=0;r=fir;
	for(i=0;i<right.size();i++)
	{
		int x=right[i];
		int val=(d[r]-d[l]+Get(r,x)-Get(l,x))/2;
		if(dir[d[r]-val]==2)
		{
			d[x]=d[r]-Get(r,x);
			t[x]=1;
			dir[d[x]]=t[x];
		}
		else
		{
			d[x]=d[l]+Get(l,x);
			t[x]=2;
			dir[d[x]]=t[x];
			r=x;
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<left.size();i++)
          ~^~~~~~~~~~~~
rail.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<right.size();i++)
          ~^~~~~~~~~~~~~
rail.cpp:26:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;fir=1;
        ^

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 20328 KB Output is correct
2 Correct 127 ms 20328 KB Output is correct
3 Correct 144 ms 22892 KB Output is correct
4 Correct 119 ms 22892 KB Output is correct
5 Correct 120 ms 22892 KB Output is correct
6 Correct 118 ms 24628 KB Output is correct
7 Correct 127 ms 28652 KB Output is correct
8 Correct 125 ms 30752 KB Output is correct
9 Correct 131 ms 30752 KB Output is correct
10 Correct 142 ms 32228 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 32228 KB Output is correct
2 Correct 117 ms 32228 KB Output is correct
3 Correct 113 ms 32228 KB Output is correct
4 Correct 111 ms 32228 KB Output is correct
5 Correct 140 ms 32228 KB Output is correct
6 Correct 128 ms 32228 KB Output is correct
7 Correct 149 ms 32228 KB Output is correct
8 Correct 143 ms 32228 KB Output is correct
9 Correct 129 ms 32228 KB Output is correct
10 Correct 160 ms 32252 KB Output is correct
11 Correct 136 ms 32252 KB Output is correct
12 Correct 129 ms 32252 KB Output is correct
13 Correct 135 ms 32252 KB Output is correct
14 Correct 130 ms 32252 KB Output is correct
15 Correct 141 ms 32252 KB Output is correct
16 Correct 134 ms 32252 KB Output is correct
17 Correct 122 ms 32252 KB Output is correct
18 Correct 135 ms 32252 KB Output is correct
19 Correct 126 ms 32252 KB Output is correct
20 Correct 109 ms 32252 KB Output is correct