이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rail.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
void findLocation(int N, int F, int pos[], int type[]) {
std::vector<int> d0(N);
d0[0] = 0;
pos[0] = F;
type[0] = 1;
std::vector<int> ord(N - 1);
for (int i = 1; i < N; i++) {
d0[i] = getDistance(0, i);
ord[i - 1] = i;
}
std::sort(ord.begin(), ord.end(), [&](int i, int j) {
return d0[i] < d0[j];
});
int S = ord[0];
type[S] = 2;
pos[S] = pos[0] + d0[S];
dbg(ord);
dbg(pos[S]);
dbg(type[S]);
std::vector<int> dS(N);
dS[0] = d0[S];
std::vector<int> left, right;
for (int i = 1; i < N; i++) {
if (i == S) continue;
int ds = getDistance(S, i);
dS[i] = ds;
if (d0[i] == d0[S] + ds) {
int located = pos[S] - ds;
if (located > pos[0]) {
pos[i] = located;
type[i] = 1;
} else {
left.push_back(i);
}
} else {
right.push_back(i);
}
}
dbg(left);
std::sort(left.begin(), left.end(), [&](int i, int j) {
return dS[i] < dS[j];
});
while (left.size()) {
// we will do that
int fr = left.front();
left.erase(left.begin());
// the front now have thingss
pos[fr] = pos[S] - dS[fr];
type[fr] = 1;
// dS[i] = dS[fr] + dfr[i] -> middle
for (int i = 0; i < (int) left.size(); i++) {
int id = left[i];
int dfr = getDistance(fr, id);
if (dfr + dS[fr] == dS[id]) {
pos[id] = pos[fr] + dfr;
type[id] = 2;
left.erase(left.begin() + i);
i--;
}
}
}
std::sort(right.begin(), right.end(), [&](int i, int j) {
return d0[i] < d0[j];
});
dbg(right);
while (right.size()) {
// we will do that
int fr = right.front();
right.erase(right.begin());
// the front now have thingss
pos[fr] = pos[0] + d0[fr];
type[fr] = 2;
dbg(fr, pos[fr], type[fr]);
for (int i = 0; i < (int) right.size(); i++) {
int id = right[i];
int dfr = getDistance(fr, id);
dbg(id, fr, dfr);
if (dfr + d0[fr] == d0[id]) {
pos[id] = pos[fr] + dfr;
type[id] = 1;
right.erase(right.begin() + i);
i--;
}
}
}
}
#ifdef LOCAL
/* This is sample grader for the contestant */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef struct Station {
int index;
int type;
int location;
int L,R;
}STATION;
long long cnt;
static int S,SUBTASK;
static STATION stations[10004];
int cmp_fun_1(const void *a,const void *b)
{
STATION c,d;
c = *(STATION*)(a);
d = *(STATION*)(b);
return c.location < d.location ? -1 : 1;
}
int cmp_fun_2(const void *a,const void *b)
{
STATION c,d;
c = *(STATION*)(a);
d = *(STATION*)(b);
return c.index < d.index ? -1 : 1;
}
void now_I_want_to_getLR(){
int now = stations[S-1].index,i;
for(i=S-2;i>=0;i--){
stations[i].R = now;
if(stations[i].type==2) now = stations[i].index;
}
now = stations[0].index;
for(i=1;i<S;i++){
stations[i].L = now;
if(stations[i].type==1) now = stations[i].index;
}
}
int getDistance(int x,int y)
{
cnt++;
if(x==y) return 0;
if(x<0 || x>=S || y<0 || y>=S) return -1;
if(stations[x].location > stations[y].location){
int tmp = x;
x = y;
y = tmp;
}
int ret = 0;
if(stations[x].type==1 && stations[y].type==1){
ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
}else if(stations[x].type==1 && stations[y].type==2){
ret = stations[y].location-stations[x].location;
}else if(stations[x].type==2 && stations[y].type==2){
ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
}else if(stations[x].type==2 && stations[y].type==1){
ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
-stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
}
return ret;
}
void getInput()
{
int g;
g = scanf("%d",&SUBTASK);
g = scanf("%d",&S);
int s;
for (s = 0; s < S; s++) {
int type, location;
g = scanf(" %d %d",&type,&location);
stations[s].index = s;
stations[s].location = location;
stations[s].type = type;
stations[s].L = -1;
stations[s].R = -1;
}
qsort(stations, S, sizeof(STATION), cmp_fun_1);
now_I_want_to_getLR();
qsort(stations, S, sizeof(STATION), cmp_fun_2);
}
int serverGetStationNumber()
{
return S;
}
int serverGetSubtaskNumber()
{
return SUBTASK;
}
int serverGetFirstStationLocation()
{
return stations[0].location;
}
int main()
{
int i;
getInput();
cnt = 0;
int location[10005];
int type[10005];
int ok = 1;
findLocation(S, serverGetFirstStationLocation(),location, type);
if(SUBTASK==3 && cnt>S*(S-1)) ok = 0;
if(SUBTASK==4 && cnt>3*(S-1)) ok = 0;
for (i = 0; i < S; i++)
if(type[i]!=stations[i].type || location[i]!=stations[i].location)
ok = 0;
if(ok==0) printf("Incorrect");
else printf("Correct");
return 0;
}
#endif
# | 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... |