| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 930621 |
2024-02-20T08:23:20 Z |
vjudge1 |
Rail (IOI14_rail) |
C++17 |
|
45 ms |
812 KB |
#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
vector<pii> getAllDists(int v, vector<int> els)
{
vector<pii> res;
for (auto el : els)
res.pb({getDistance(v, el), el});
return res;
}
vector<int> loc, tp;
int n;
pii doStuff(int v, int T)
{
vector<pii> vals;
{
vector<int> bf;
for (int i = 0; i < n; ++i)
if (!tp[i])
bf.pb(i);
vals = getAllDists(v, bf);
sort(vals.begin(), vals.end());
}
if (vals.size() == 0)
return {-1, -1};
int curClosing = vals[0].s;
int curD = vals[0].f;
tp[curClosing] = 2 - T;
loc[curClosing] = (T ? loc[v] - vals[0].f : loc[v] + vals[0].f);
for (int i = 1; i < vals.size(); ++i)
{
if (vals[i].f > getDistance(curClosing, vals[i].s))
break;
curClosing = vals[i].s;
curD = vals[i].f;
tp[curClosing] = 2 - T;
loc[curClosing] = (T ? loc[v] - vals[i].f : loc[v] + vals[i].f);
}
return {curClosing, curD};
}
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
loc.resize(N);
tp.resize(N);
loc[0] = first;
tp[0] = 1;
if (N != 1)
{
pii closing0 = doStuff(0, 0);
pii newOpen = doStuff(closing0.f, 1);
if (newOpen.f != -1 and closing0.s > newOpen.s)
{
pii bf = doStuff(newOpen.f, 0);
if (bf.f != -1)
doStuff(bf.f, 1);
}
}
for (int i = 0; i < N; ++i)
location[i] = loc[i], stype[i] = tp[i];
}
// /* 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 'std::pair<int, int> doStuff(int, int)':
rail.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 1; i < vals.size(); ++i)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
520 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
520 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
