Submission #945759

#	Time	Username	Problem	Language	Result	Execution time	Memory
945759		WongChun1234	Rail (IOI14_rail)	C++14	0 / 100	443 ms	94864 KiB

rail

#include<bits/stdc++.h>
#include"rail.h"
using namespace std;
 
const int N=5050;
int dist[N][4],rf,rrf;
vector<pair<int,int>> srt,ans,l,r;
map<int,int> id;
 
void eat(int i,int pos,int ty){
	//cerr<<i<<" at pos "<<pos<<" type "<<ty<<endl;
	ans[i]={pos,ty};
	id[pos]=i;
}
void findLocation(int n, int first, int location[], int stype[]) {
	int q=100000050;
	ans.resize(n);
	for (int i=-1000000;i<=1000000;i++) id[i]=5049;
	for (int i=1;i<n;i++){
		dist[i][0]=getDistance(0,i);
		srt.push_back({dist[i][0],i});
	}
	sort(srt.begin(),srt.end());
	rrf=rf=srt[0].second;
	eat(0,0,1);
	eat(rf,srt[0].first,2);
	for (int i=1;i<n;i++){
		if (i==rf) continue;
		dist[i][1]=getDistance(rf,i);
		if (dist[i][1]+dist[rf][0]==dist[i][0]){
			l.push_back({dist[i][1],i});
		}else{
			r.push_back({dist[i][0],i});
		}
	}
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	for (pair<int,int> i:r){
		cerr<<i.first<<" "<<i.second<<" !!\n";
		int dis,ps;
		dist[i.second][2]=getDistance(rf,i.second);
		assert(!((dist[i.second][2]+dist[rf][0]-dist[i.second][0])%2));
		dis=(dist[i.second][2]+dist[rf][0]-dist[i.second][0])/2;
		ps=dist[rf][0]-dis;
		if (ans[id[ps]].second==1){
			//          -------------->
			//          |----
			// ------------->
			eat(i.second,dist[i.second][0],2);
			rf=i.second;
		}else{
			//      <---------
			//           D   |
			// -------------->
			eat(i.second,dist[rf][0]-dist[i.second][2],1);
		}
	}
	if (l.size()){
		rf=l[0].second;
		eat(rf,dist[rrf][0]-dist[rf][1],1);
		l.erase(l.begin(),next(l.begin()));
		for (pair<int,int> i:l){
			cerr<<i.first<<" "<<i.second<<" ??\n";
			int dis,ps;
			dist[i.second][2]=getDistance(rf,i.second);
			assert(!((dist[i.second][2]+dist[rf][0]-dist[i.second][0])%2));
			dis=(dist[i.second][2]+dist[rf][0]-dist[i.second][0])/2;
			ps=ans[rf].first+dis;
			if (ans[id[ps]].second==2){
				//     <--------------D
				//     |----       ----
				// <--------
				eat(i.second,dist[rrf][0]-dist[i.second][1],1);
				rf=i.second;
			}else{
				// <------------------D
				// |    C          ----
				// -------->
				eat(i.second,ans[rf].first+dist[i.second][2],2);
			}
		}
	}
	int mn=ans[0].first-first;
	for (int i=0;i<n;i++){
		location[i]=ans[i].first+mn;
		stype[i]=ans[i].second;
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:16:6: warning: unused variable 'q' [-Wunused-variable]
   16 |  int q=100000050;
      |      ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44