oj.uz

Submission #706402

# Submission time Handle Problem Language Result Execution time Memory
706402 2023-03-06T12:52:20 Z jamezzz Rail (IOI14_rail) C++17
100 / 100
 92 ms 1004 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

#define maxn 10005

int dist[maxn];
vector<int> stuff[maxn];
vector<ii> v,l,r;

void findLocation(int N,int first,int location[],int stype[]){
	location[0]=first;stype[0]=1;
	for(int i=1;i<N;++i){
		location[i]=-1;
		dist[i]=getDistance(0,i);
		v.pb({dist[i],i});
	}
	sort(all(v),greater<ii>());
	//printf("v: ");
	//for(auto[a,b]:v)printf("(%d %d) ",a,b);
	//printf("\n");
	
	int second=v.back().se;
	location[second]=first+dist[second];
	stype[second]=2;
	v.pop_back();
	
	while(!v.empty()){
		auto[d,x]=v.back();
		v.pop_back();
		if(dist[x]==dist[second]+getDistance(second,x))l.pb({d,x});
		else r.pb({d,x});
	}
	//printf("l: ");
	//for(auto[a,b]:l)printf("(%d %d) ",a,b);
	//printf("\n");
	//printf("r: ");
	//for(auto[a,b]:r)printf("(%d %d) ",a,b);
	//printf("\n");
	
	int pv=-1;
	for(int i=0;i<r.size();++i){
		//printf("%d: %d %d, pv=%d\n",i,r[i].fi,r[i].se,pv);
		auto[_,x]=r[i];
		if(pv==-1){
			location[x]=first+dist[x];
			stype[x]=2;
			pv=x;
			continue;
		}
		int tmp=getDistance(pv,x);
		if(dist[x]==dist[pv]+tmp){
			location[x]=location[pv]-tmp;
			stype[x]=1;
		}
		else{
			int extra=(dist[pv]+tmp-dist[x])/2;
			bool found=false;
			//printf("extra %d\n",extra);
			for(int i=0;i<N;++i){
				if(location[i]!=-1&&location[i]==location[pv]-extra){
					//printf("found: %d\n",i);
					found=true;
					if(stype[i]==1){
						location[x]=first+dist[x];
						stype[x]=2;
						pv=x;
					}
					else{
						location[x]=location[pv]-tmp;
						stype[x]=1;
					}
					break;
				}
			}
			if(!found){
				location[x]=first+dist[x];
				stype[x]=2;
				pv=x;
			}
		}
	}
	
	pv=-1;
	for(int i=0;i<l.size();++i){
		//printf("%d: %d %d, pv=%d\n",i,l[i].fi,l[i].se,pv);
		auto[_,x]=l[i];
		if(pv==-1){
			location[x]=location[second]-dist[x]+dist[second];
			stype[x]=1;
			pv=x;
			continue;
		}
		int tmp=getDistance(pv,x);
		if(dist[x]==dist[pv]+tmp){
			location[x]=location[pv]+tmp;
			stype[x]=2;
		}
		else{
			int extra=(dist[pv]+tmp-dist[x])/2;
			//printf("extra %d (%d+%d-%d)/2\n",extra,dist[pv],tmp,dist[x]);
			bool found=false;
			for(int i=0;i<N;++i){
				if(location[i]!=-1&&location[i]==location[pv]+extra){
					//printf("found: %d\n",i);
					found=true;
					if(stype[i]==1){
						location[x]=location[pv]+tmp;
						stype[x]=2;
					}
					else{
						location[x]=location[second]-dist[x]+dist[second];
						stype[x]=1;
						pv=x;
					}
					break;
				}
			}
			if(!found){
				location[x]=location[second]-dist[x]+dist[second];
				stype[x]=1;
				pv=x;
			}
		}
	}
	
	//printf("ans:\n");
	//for(int i=0;i<N;++i)printf("%d ",location[i]);printf("\n");
	//for(int i=0;i<N;++i)printf("%d ",stype[i]);printf("\n");
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<r.size();++i){
      |              ~^~~~~~~~~
rail.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=0;i<l.size();++i){
      |              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 836 KB Output is correct
2 Correct 88 ms 900 KB Output is correct
3 Correct 85 ms 872 KB Output is correct
4 Correct 88 ms 844 KB Output is correct
5 Correct 86 ms 876 KB Output is correct
6 Correct 89 ms 872 KB Output is correct
7 Correct 88 ms 884 KB Output is correct
8 Correct 87 ms 872 KB Output is correct
9 Correct 86 ms 876 KB Output is correct
10 Correct 91 ms 844 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 824 KB Output is correct
2 Correct 87 ms 896 KB Output is correct
3 Correct 86 ms 864 KB Output is correct
4 Correct 86 ms 884 KB Output is correct
5 Correct 85 ms 884 KB Output is correct
6 Correct 91 ms 844 KB Output is correct
7 Correct 89 ms 872 KB Output is correct
8 Correct 86 ms 884 KB Output is correct
9 Correct 86 ms 868 KB Output is correct
10 Correct 86 ms 900 KB Output is correct
11 Correct 87 ms 896 KB Output is correct
12 Correct 92 ms 880 KB Output is correct
13 Correct 87 ms 872 KB Output is correct
14 Correct 90 ms 876 KB Output is correct
15 Correct 88 ms 872 KB Output is correct
16 Correct 86 ms 1004 KB Output is correct
17 Correct 87 ms 844 KB Output is correct
18 Correct 86 ms 876 KB Output is correct
19 Correct 86 ms 888 KB Output is correct
20 Correct 86 ms 904 KB Output is correct