| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 945757 | WongChun1234 | Rail (IOI14_rail) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 find_location(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;
}
}