#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int c,d;
int a[5001],b[5001];
int qc[5001],qd[5001];
int loc[1000001];
vector<int>l,r;
stack<int>s;
bool cmp(int x,int y){
return qc[x]<qc[y];
}
void findLocation(int N, int first, int location[], int stype[]){
n=N;
for(int i=0; i<n ;i++){
a[i]=b[i]=qc[i]=qd[i]=0;
}
l.clear();r.clear();
c=0;a[c]=first;b[c]=1;loc[a[c]]=1;
int d=1;
for(int i=0; i<n ;i++){
if(i!=c) qc[i]=getDistance(c,i);
if(i!=c && qc[i]<qc[d]) d=i;
}
a[d]=a[c]+qc[d];b[d]=2;loc[a[d]]=2;
for(int i=0; i<n ;i++){
if(i==c) qd[i]=qc[d];
else if(i!=d) qd[i]=getDistance(d,i);
if(i!=d && qd[i]<qd[c]) c=i;
}
for(int i=0; i<n ;i++) if(i!=0 && i!=c) qc[i]-=qd[0]-qd[c];
swap(qc[0],qc[c]);
a[c]=a[d]-qd[c];b[c]=1;loc[a[c]]=1;
for(int i=0; i<n ;i++){
if(i==c || i==d) continue;
if(qc[i]>qd[i]) l.push_back(i);
else r.push_back(i);
}
s.push(c);
sort(l.begin(),l.end(),cmp);
for(auto x:l){
if(x==l[0]){
a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
s.push(x);
continue;
}
int y=s.top();
int dis=getDistance(y,x);
int r=(qd[y]+dis-qd[x])/2+a[y];
if(loc[r]!=1){
a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
s.push(x);
}
else{
a[x]=a[y]+dis;b[x]=2;loc[a[x]]=2;
}
}
while(!s.empty()) s.pop();
sort(r.begin(),r.end(),cmp);
s.push(d);
for(auto x:r){
if(x==r[0]){
a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
s.push(x);
continue;
}
int y=s.top();
int dis=getDistance(y,x);
int r=a[y]-(qc[y]+dis-qc[x])/2;
if(loc[r]!=2){
a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
s.push(x);
}
else{
a[x]=a[y]-dis;b[x]=1;loc[a[x]]=1;
}
}
for(int i=0; i<n ;i++) loc[a[i]]=0;
for(int i=0; i<n ;i++) location[i]=a[i],stype[i]=b[i];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
372 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
4180 KB |
Output is correct |
2 |
Correct |
90 ms |
4352 KB |
Output is correct |
3 |
Correct |
87 ms |
4488 KB |
Output is correct |
4 |
Correct |
89 ms |
4396 KB |
Output is correct |
5 |
Correct |
88 ms |
4344 KB |
Output is correct |
6 |
Correct |
88 ms |
4344 KB |
Output is correct |
7 |
Correct |
89 ms |
4224 KB |
Output is correct |
8 |
Correct |
90 ms |
4344 KB |
Output is correct |
9 |
Correct |
88 ms |
4472 KB |
Output is correct |
10 |
Correct |
89 ms |
4356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
4216 KB |
Output is correct |
2 |
Correct |
88 ms |
4356 KB |
Output is correct |
3 |
Correct |
89 ms |
4600 KB |
Output is correct |
4 |
Correct |
87 ms |
4392 KB |
Output is correct |
5 |
Correct |
88 ms |
4472 KB |
Output is correct |
6 |
Correct |
87 ms |
4220 KB |
Output is correct |
7 |
Correct |
88 ms |
4216 KB |
Output is correct |
8 |
Correct |
87 ms |
4472 KB |
Output is correct |
9 |
Correct |
89 ms |
4472 KB |
Output is correct |
10 |
Correct |
90 ms |
4344 KB |
Output is correct |
11 |
Correct |
87 ms |
4224 KB |
Output is correct |
12 |
Correct |
87 ms |
4344 KB |
Output is correct |
13 |
Correct |
88 ms |
4352 KB |
Output is correct |
14 |
Correct |
88 ms |
4344 KB |
Output is correct |
15 |
Correct |
89 ms |
4364 KB |
Output is correct |
16 |
Correct |
88 ms |
4488 KB |
Output is correct |
17 |
Correct |
88 ms |
4472 KB |
Output is correct |
18 |
Correct |
89 ms |
4344 KB |
Output is correct |
19 |
Correct |
90 ms |
4472 KB |
Output is correct |
20 |
Correct |
89 ms |
4460 KB |
Output is correct |