#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
vector<vector<long long>> dists;
vector<long long> loc, tp, shortest;
int n;
// int C = 0;
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
loc.resize(N);
tp.resize(N);
dists.resize(N, vector<long long>(N));
shortest.resize(N, 2e9 + 10);
loc[0] = first;
tp[0] = 1;
vector<int> dist0(N);
vector<pair<long long, long long>> vals0;
for (long long i = 1; i < n; ++i)
{
vals0.pb({getDistance(0, i), i});
dist0[i] = vals0.back().f;
}
sort(all(vals0));
if (N != 1)
{
long long closing = vals0.begin()->s;
tp[closing] = 2;
loc[closing] = loc[0] + vals0.begin()->f;
long long distBetween = vals0.begin()->f;
vector<long long> distC(n);
vector<pair<long long, long long>> valsC;
for (long long i = 1; i < n; ++i)
if (i != closing)
{
distC[i] = getDistance(closing, i);
valsC.pb({distC[i], i});
}
sort(all(valsC));
{
// long long lastOpening = min(distBetween, valsC[0].f) == distBetween ? 0LL : valsC[0].s, lastClosing = closing;
long long lastOpening = 0;
vector<ll> openingBrackets;
openingBrackets.pb(0);
for (auto [dist, el] : valsC)
{
if (dist0[el] == distC[el] + distBetween)
if (dist < distBetween)
{
openingBrackets.pb(el);
tp[el] = 1;
loc[el] = loc[closing] - dist;
}
else
{
long long X = getDistance(lastOpening, el);
bool found = false;
for (auto cur : openingBrackets)
if (distC[el] == distC[cur] + (X - (loc[cur] - loc[lastOpening])) and (X - (loc[cur] - loc[lastOpening])) > 0)
found = true;
if (found)
{
tp[el] = 2;
loc[el] = loc[lastOpening] + X;
}
else
{
openingBrackets.pb(el);
tp[el] = 1;
loc[el] = loc[closing] - distC[el];
lastOpening = el;
}
}
}
}
{
long long lastClosing = closing;
vector<ll> closingBrackets;
closingBrackets.pb(closing);
for (auto [dist, el] : valsC)
{
if (!tp[el])
{
long long X = getDistance(lastClosing, el);
bool found = false;
for (auto cur : closingBrackets)
if (dist0[el] == dist0[cur] + (X - (loc[lastClosing] - loc[cur])) and (X - (loc[lastClosing] - loc[cur])) > 0)
found = true;
if (found)
{
tp[el] = 1;
loc[el] = loc[lastClosing] - X;
}
else
{
closingBrackets.pb(el);
tp[el] = 2;
loc[el] = loc[0] + dist0[el];
lastClosing = el;
}
}
}
}
}
for (long long i = 0; i < n; ++i)
{
location[i] = loc[i];
stype[i] = tp[i];
// cout << stype[i] << " " << location[i] << " " << i << "!\n";
}
}
// /* This is sample grader for the contestant */
// #include <unistd.h>
// #include <stdlib.h>
// #include <stdio.h>
// #include <string.h>
// #include <assert.h>
// #include "rail.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;
// }
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:62:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
62 | if (dist0[el] == distC[el] + distBetween)
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
133 ms |
197024 KB |
Output is correct |
2 |
Correct |
120 ms |
196820 KB |
Output is correct |
3 |
Correct |
122 ms |
196940 KB |
Output is correct |
4 |
Correct |
125 ms |
196944 KB |
Output is correct |
5 |
Correct |
122 ms |
197028 KB |
Output is correct |
6 |
Correct |
123 ms |
196996 KB |
Output is correct |
7 |
Correct |
121 ms |
196948 KB |
Output is correct |
8 |
Correct |
117 ms |
196796 KB |
Output is correct |
9 |
Correct |
119 ms |
196980 KB |
Output is correct |
10 |
Correct |
120 ms |
196984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
196996 KB |
Output is correct |
2 |
Correct |
119 ms |
196816 KB |
Output is correct |
3 |
Correct |
118 ms |
196944 KB |
Output is correct |
4 |
Correct |
119 ms |
196984 KB |
Output is correct |
5 |
Correct |
121 ms |
197000 KB |
Output is correct |
6 |
Correct |
125 ms |
196948 KB |
Output is correct |
7 |
Correct |
124 ms |
196944 KB |
Output is correct |
8 |
Correct |
130 ms |
197284 KB |
Output is correct |
9 |
Correct |
120 ms |
196928 KB |
Output is correct |
10 |
Correct |
120 ms |
196908 KB |
Output is correct |
11 |
Correct |
125 ms |
196948 KB |
Output is correct |
12 |
Correct |
123 ms |
197000 KB |
Output is correct |
13 |
Correct |
120 ms |
196944 KB |
Output is correct |
14 |
Correct |
123 ms |
196932 KB |
Output is correct |
15 |
Correct |
118 ms |
196944 KB |
Output is correct |
16 |
Correct |
124 ms |
197008 KB |
Output is correct |
17 |
Correct |
124 ms |
196988 KB |
Output is correct |
18 |
Correct |
122 ms |
196988 KB |
Output is correct |
19 |
Correct |
123 ms |
196944 KB |
Output is correct |
20 |
Correct |
127 ms |
196984 KB |
Output is correct |