oj.uz

Submission #81092

# Submission time Handle Problem Language Result Execution time Memory
81092 2018-10-23T18:45:16 Z giorgikob Rail (IOI14_rail) C++14
100 / 100
 197 ms 2264 KB 
#include "rail.h"
#include<bits/stdc++.h>

#define F first
#define Se second
using namespace std;
vector<pair<int,int> >V;
int D[100000],D1[100000];
void findLocation(int n, int first, int location[], int stype[])
{
	for(int i=0;i<n;i++)location[i]=-1;
	location[0]=first;stype[0]=1;
	for(int i=1;i<n;i++)
	{
		int X=getDistance(0,i);
		D[i]=X;
		V.push_back(make_pair(X,i));
	}
	sort(V.begin(),V.end());
	int x=V[0].F,A=0,B=V[0].Se,Ax=first,Bx=first+x;
	location[B]=Bx;stype[B]=2;
	
	D1[0]=D[B];
	for(int i=1;i<n;i++)
	if(i!=B)
	D1[i]=getDistance(B,i);
	
	int distAB=D[B],left=0,right=B;
	for(int i=1;i<V.size();i++)
	{
		int distA=V[i].F,ind=V[i].Se;
		int distB=D1[ind];
//		cout<<ind<<" "<<distA<<" "<<distB<<"<--------"<<endl;
		if(distB<distAB && distA==distB+distAB)
		{
			location[ind]=location[B]-distB;
			stype[ind]=1;
		}
		else
		if(distAB+distB==distA)
		{
			//cout<<ind<<endl;
			int dist_left=getDistance(left,ind);
			int distB_left=D1[left];
			int loc=location[left]+dist_left;
			if(loc>=location[B])
			{
				location[ind]=location[B]-distB;
				stype[ind]=1;
				left=ind;
			}
			else
			{
				//cout<<ind<<" "<<loc<<endl;
				int in=-1,mxlc=-1;
				for(int j=0;j<n;j++)
				if(location[j]>=0)
				if(location[j]<loc && mxlc<location[j])
				in=j,mxlc=location[j];//cout<<in<<endl;
				if(in==-1)
				{
					location[ind]=location[B]-distB;
					stype[ind]=1;
					left=ind;
				}
				else
				if(D1[in]+(dist_left-(location[in]-location[left]))==distB)
				{
					location[ind]=loc;
					stype[ind]=2;
				}
				else
				{
					location[ind]=location[B]-distB;
					stype[ind]=1;
					left=ind;
				}
			}
		}
		else
		{
			int dist_right=getDistance(right,ind);
			int distA_right=D[right];
			int loc=location[right]-dist_right;
			if(loc<=location[B])
			{
				location[ind]=location[A]+distA;
				stype[ind]=2;
				right=ind;
			}
			else
			{
				int in=-1,mxlc=1e9;
				for(int j=0;j<n;j++)
				if(location[j]>=0)
				if(location[j]>loc && location[j]<mxlc)
				in=j,mxlc=location[j];
				if(in==-1)
				{
					location[ind]=location[A]+distA;
					stype[ind]=2;
					right=ind;
				}
				else
				if(D[in]+(dist_right-(location[right]-location[in]))==distA)
				{
					location[ind]=loc;
					stype[ind]=1;
				}
				else
				{
					location[ind]=location[A]+distA;
					stype[ind]=2;
					right=ind;
				}
			}
		}
		
	}
	//for(int i=0;i<n;i++)
	//cout<<i<<" "<<location[i]<<" "<<stype[i]<<endl;
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<V.size();i++)
              ~^~~~~~~~~
rail.cpp:44:8: warning: unused variable 'distB_left' [-Wunused-variable]
    int distB_left=D1[left];
        ^~~~~~~~~~
rail.cpp:83:8: warning: unused variable 'distA_right' [-Wunused-variable]
    int distA_right=D[right];
        ^~~~~~~~~~~
rail.cpp:20:29: warning: unused variable 'Ax' [-Wunused-variable]
  int x=V[0].F,A=0,B=V[0].Se,Ax=first,Bx=first+x;
                             ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 908 KB Output is correct
2 Correct 121 ms 908 KB Output is correct
3 Correct 117 ms 1088 KB Output is correct
4 Correct 123 ms 1092 KB Output is correct
5 Correct 117 ms 1156 KB Output is correct
6 Correct 120 ms 1340 KB Output is correct
7 Correct 121 ms 1340 KB Output is correct
8 Correct 119 ms 1340 KB Output is correct
9 Correct 123 ms 1340 KB Output is correct
10 Correct 120 ms 1524 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 1524 KB Output is correct
2 Correct 123 ms 1524 KB Output is correct
3 Correct 119 ms 1524 KB Output is correct
4 Correct 126 ms 1552 KB Output is correct
5 Correct 125 ms 1584 KB Output is correct
6 Correct 120 ms 1628 KB Output is correct
7 Correct 124 ms 1800 KB Output is correct
8 Correct 120 ms 1800 KB Output is correct
9 Correct 197 ms 1836 KB Output is correct
10 Correct 125 ms 1836 KB Output is correct
11 Correct 120 ms 1896 KB Output is correct
12 Correct 120 ms 1896 KB Output is correct
13 Correct 121 ms 2072 KB Output is correct
14 Correct 122 ms 2088 KB Output is correct
15 Correct 139 ms 2088 KB Output is correct
16 Correct 121 ms 2196 KB Output is correct
17 Correct 116 ms 2196 KB Output is correct
18 Correct 122 ms 2200 KB Output is correct
19 Correct 118 ms 2212 KB Output is correct
20 Correct 119 ms 2264 KB Output is correct