이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int d[maxn][maxn];
int n;
int a[maxn];
int ans[maxn];
inline int calc(int u, int v)
{
if (u>v) swap(u,v);
if (d[u][v] == -1) d[u][v] = getDistance(u,v);
return d[u][v];
}
bool cmp(int x, int y)
{
return calc(0,x)<calc(0,y);
}
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
for (int i=0; i<n; i++) stype[i] = ans[i] = -1;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j] = -1;
ans[0] = first;
for (int i=1; i<n; i++)
{
int temp = calc(0,i);
a[i] = i;
}
ans[0] = first;
sort(a+1,a+n,cmp);
int L = 0; int R = a[1];
ans[R] = ans[L] + calc(L,R);
stype[R] = 1;
stype[L] = 0;
// for (int i=1; i<n; i++) cerr<<calc(0,i)<<' '; cerr<<endl;
// cerr<<first<<' '<<n<<endl;
for (int i=2; i<n; i++)
{
int val = calc(L,a[i]);
// cerr<<L<<','<<ans[L]<<' '<<R<<','<<ans[R]<<" = "<<a[i]<<'\n';
/** L k R
( ) ) **/
int pos = ans[L] + val;
// cerr<<pos<<"!!\n";
if (pos<ans[R])
{
int p = -1;
for (int j=0; j<n; j++)
if (ans[j]!=-1&&stype[j]==0&&ans[j]<pos&&(p==-1||ans[p] < ans[j])) p = j;
// cerr<<p<<endl;
// cerr<<calc(a[i],R)<<' '<<pos-ans[p]+ans[R]-ans[p]<<endl;
if (p!=-1&&calc(a[i],R) == pos - ans[p] + ans[R] - ans[p])
{
ans[a[i]] = pos;
stype[a[i]] = 1;
continue;
}
}
else /**
L R k
( ) )
**/
if (pos>ans[R])
{
int p = -1;
// for (int j=0; j<n; j++) cerr<<ans[j]<<":"<<stype[j]<<" "; cerr<<'\n';
for (int j=0; j<n; j++)
if (ans[j]!=-1&&stype[j]==0&&ans[j]<ans[R]&&(p==-1||ans[p] < ans[j])) p = j;
// cerr<<p<<endl;
if (p!=-1&&calc(a[i],R) == pos - ans[p] + ans[R] - ans[p])
{
ans[a[i]] = pos;
stype[a[i]] = 1;
R = a[i];
continue;
}
// cerr<<":<"<<endl;
}
val = calc(a[i],R);
pos = ans[R] - val;
// cerr<<val<<' '<<pos<<" @@ "<<endl;
/** L k R
( ( ) **/
if (pos > ans[L])
{
int p = -1;
for (int j=0; j<n; j++)
if (ans[j]!=-1&&ans[j] > pos&&stype[j]==1&&(p==-1||ans[p] > ans[j])) p=j;
if (p!=-1&&calc(a[i],L) == 2*ans[p] - pos - ans[L])
{
ans[a[i]]=pos;
stype[a[i]] = 0;
continue;
}
}
else/**
k L R
( ( )
**/
if (pos<ans[L])
{
int p = -1;
for (int j=0; j<n; j++)
if (ans[j]!=-1&&ans[j] > ans[L]&&stype[j]==1&&(p==-1||ans[p] > ans[j])) p=j;
if (p!=-1&&calc(a[i],L) == 2*ans[p] - pos - ans[L])
{
ans[a[i]]=pos;
stype[a[i]] = 0;
L = a[i];
continue;
}
}
assert(false);
}
for (int i=0; i<n; i++) stype[i] ++;
ans[0] = first;
for (int i=0; i<n; i++) location[i] = ans[i];
return;
}
컴파일 시 표준 에러 (stderr) 메시지
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:13: warning: unused variable 'temp' [-Wunused-variable]
29 | int temp = calc(0,i);
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |