| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 741653 |
2023-05-14T13:57:10 Z |
marvinthang |
Rail (IOI14_rail) |
C++17 |
|
80 ms |
588 KB |
/*************************************
* author: marvinthang *
* created: 14.05.2023 18:29:29 *
*************************************/
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i--; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
void findLocation(int N, int first, int location[], int stype[]) {
vector <int> dist0(N);
location[0] = first; stype[0] = 1;
FOR(i, 1, N) {
stype[i] = 0;
dist0[i] = getDistance(0, i);
}
vector <int> pos(N - 1);
vector <int> distp(N);
iota(ALL(pos), 1);
sort(ALL(pos), [&] (int a, int b) { return dist0[a] < dist0[b]; });
int p = pos[0];
stype[p] = 2;
location[p] = first + dist0[p];
vector <int> left, right;
for (int u: pos) if (u != p) {
distp[u] = getDistance(p, u);
if (dist0[u] == dist0[p] + distp[u]) {
if (distp[u] < dist0[p]) {
stype[u] = 1;
location[u] = location[p] - distp[u];
} else left.push_back(u);
} else right.push_back(u);
}
vector <int> up;
for (int u: right) {
if (up.empty()) {
up.push_back(u);
stype[u] = 2;
location[u] = location[0] + dist0[u];
continue;
}
int f = getDistance(up.back(), u);
int pos = -1;
for (int u: up) if (location[u] >= location[up.back()] - f) {
pos = u;
break;
}
assert(pos != -1);
int t = f - (location[up.back()] - location[pos]);
if (dist0[u] == dist0[pos] + t) {
stype[u] = 1;
location[u] = location[up.back()] - f;
} else {
stype[u] = 2;
location[u] = location[0] + dist0[u];
up.push_back(u);
}
}
vector <int> down;
for (int u: left) {
if (down.empty()) {
stype[u] = 1;
location[u] = location[p] - distp[u];
down.push_back(u);
continue;
}
int f = getDistance(down.back(), u);
int pos = -1;
for (int u: down) if (location[u] <= location[down.back()] + f) {
pos = u;
break;
}
assert(pos != -1);
int t = f - (location[pos] - location[down.back()]);
if (distp[u] == distp[pos] + t) {
stype[u] = 2;
location[u] = location[down.back()] + f;
} else {
stype[u] = 1;
location[u] = location[p] - distp[u];
down.push_back(u);
}
}
// REP(i, N) cout << stype[i] << ' ' << location[i] << '\n';
}
#ifdef LOCAL
/* 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;
}
int seed;
mt19937 rng;
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); }
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); }
void getInput()
{
int g;
seed = chrono::steady_clock::now().time_since_epoch().count();
S = 100;
rng.seed(seed);
// cout << seed << '\n';
SUBTASK = 4;
// g = scanf("%d",&S);
int s;
vector <int> pos(1000);
iota(ALL(pos), 1);
for (s = 0; s < S; s++) {
int type, location, p;
if (s == 1) {
type = 1; location = 0;
} else if (s == 2) {
type = 2; location = 1100;
} else {
p = rand(pos.size());
location = pos[p];
pos.erase(pos.begin() + p);
type = !s ? 1 : rand(1, 2);
}
// g = scanf(" %d %d",&type,&location);
// cout << type << ' ' << location << endl;
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()
{
file("rail");
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 |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
388 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
516 KB |
Output is correct |
| 2 |
Correct |
67 ms |
516 KB |
Output is correct |
| 3 |
Correct |
67 ms |
520 KB |
Output is correct |
| 4 |
Correct |
67 ms |
588 KB |
Output is correct |
| 5 |
Correct |
75 ms |
496 KB |
Output is correct |
| 6 |
Correct |
69 ms |
500 KB |
Output is correct |
| 7 |
Correct |
79 ms |
500 KB |
Output is correct |
| 8 |
Correct |
68 ms |
512 KB |
Output is correct |
| 9 |
Correct |
66 ms |
500 KB |
Output is correct |
| 10 |
Correct |
68 ms |
516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
572 KB |
Output is correct |
| 2 |
Correct |
67 ms |
512 KB |
Output is correct |
| 3 |
Correct |
72 ms |
504 KB |
Output is correct |
| 4 |
Correct |
67 ms |
516 KB |
Output is correct |
| 5 |
Correct |
69 ms |
500 KB |
Output is correct |
| 6 |
Correct |
75 ms |
492 KB |
Output is correct |
| 7 |
Correct |
77 ms |
512 KB |
Output is correct |
| 8 |
Correct |
72 ms |
496 KB |
Output is correct |
| 9 |
Correct |
70 ms |
500 KB |
Output is correct |
| 10 |
Correct |
67 ms |
504 KB |
Output is correct |
| 11 |
Correct |
72 ms |
500 KB |
Output is correct |
| 12 |
Correct |
68 ms |
508 KB |
Output is correct |
| 13 |
Correct |
68 ms |
496 KB |
Output is correct |
| 14 |
Correct |
80 ms |
500 KB |
Output is correct |
| 15 |
Correct |
69 ms |
512 KB |
Output is correct |
| 16 |
Correct |
68 ms |
508 KB |
Output is correct |
| 17 |
Correct |
74 ms |
500 KB |
Output is correct |
| 18 |
Correct |
73 ms |
500 KB |
Output is correct |
| 19 |
Correct |
70 ms |
512 KB |
Output is correct |
| 20 |
Correct |
73 ms |
588 KB |
Output is correct |
