# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
599996 |
2022-07-20T11:24:26 Z |
8e7 |
철로 (IOI14_rail) |
C++17 |
|
80 ms |
1612 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
bool found[maxn];
void findLocation(int N, int first, int location[], int stype[]) {
vector<int> dl(N, 0), dr(N, 0);
dl[0] = inf;
for (int i = 1;i < N;i++) {
dl[i] = getDistance(0, i);
}
location[0] = first;
stype[0] = 1;
if (N == 1) return;
int rid = min_element(dl.begin(), dl.end()) - dl.begin();
dr[rid] = inf;
int llen = dl[rid];
location[rid] = first + dl[rid];
stype[rid] = 2;
vector<pii> vl, vr;
debug("rid", rid);
for (int i = 0;i < N;i++) {
if (i != rid) {
dr[i] = getDistance(rid, i);
if (!i) continue;
if (dl[i] - dr[i] == llen) {
if (dr[i] < llen) {
location[i] = location[rid] - dr[i];
stype[i] = 1;
} else {
vl.push_back({dr[i], i});
}
debug("lef", i);
}
}
}
int lid = min_element(dr.begin(), dr.end()) - dr.begin();
for (int i = 0;i < N;i++) {
if (i == rid) dl[i] = dr[lid];
else if (i && dl[i] - dr[i] != llen) {
debug("rig", i);
dl[i] = dr[i] - dr[lid];
vr.push_back({dl[i], i});
}
}
debug("lid", lid, "rid", rid);
sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());
int lef = 0, rig = rid;
for (auto [dis, id]:vl) {
int p = getDistance(lef, id), guess = location[lef] + p;
int x = (dis - (location[rid] - guess)) / 2;
if (guess - x >= 0 && found[guess - x]) {
location[id] = guess;
stype[id] = 2;
} else {
location[id] = location[rid] - dis;
found[location[id]] = 1;
stype[id] = 1;
lef = id;
}
}
for (auto [dis, id]:vr) {
int p = getDistance(rig, id), guess = location[rig] - p;
int x = (dis - (guess - location[lid])) / 2;
if (guess + x < maxn && found[guess + x]) {
location[id] = guess;
stype[id] = 1;
} else {
location[id] = location[lid] + dis;
found[location[id]] = 1;
stype[id] = 2;
rig = id;
}
}
pary(stype,stype + N);
pary(location, location + N);
}
/*
2 7
1 30
2 31
1 17
1 20
2 21
2 22
2 23
*/
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
rail.cpp:41:2: note: in expansion of macro 'debug'
41 | debug("rid", rid);
| ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
rail.cpp:53:5: note: in expansion of macro 'debug'
53 | debug("lef", i);
| ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
rail.cpp:61:4: note: in expansion of macro 'debug'
61 | debug("rig", i);
| ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
rail.cpp:66:2: note: in expansion of macro 'debug'
66 | debug("lid", lid, "rid", rid);
| ^~~~~
rail.cpp:14:19: warning: statement has no effect [-Wunused-value]
14 | #define pary(...) 0
| ^
rail.cpp:96:2: note: in expansion of macro 'pary'
96 | pary(stype,stype + N);
| ^~~~
rail.cpp:14:19: warning: statement has no effect [-Wunused-value]
14 | #define pary(...) 0
| ^
rail.cpp:97:2: note: in expansion of macro 'pary'
97 | pary(location, location + N);
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
380 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 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 |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
0 ms |
380 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
1408 KB |
Output is correct |
2 |
Correct |
66 ms |
1524 KB |
Output is correct |
3 |
Correct |
64 ms |
1540 KB |
Output is correct |
4 |
Correct |
66 ms |
1524 KB |
Output is correct |
5 |
Correct |
66 ms |
1524 KB |
Output is correct |
6 |
Correct |
76 ms |
1544 KB |
Output is correct |
7 |
Correct |
78 ms |
1528 KB |
Output is correct |
8 |
Correct |
67 ms |
1528 KB |
Output is correct |
9 |
Correct |
69 ms |
1528 KB |
Output is correct |
10 |
Correct |
66 ms |
1536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
1400 KB |
Output is correct |
2 |
Correct |
70 ms |
1524 KB |
Output is correct |
3 |
Correct |
64 ms |
1524 KB |
Output is correct |
4 |
Correct |
65 ms |
1528 KB |
Output is correct |
5 |
Correct |
66 ms |
1540 KB |
Output is correct |
6 |
Correct |
65 ms |
1536 KB |
Output is correct |
7 |
Correct |
66 ms |
1408 KB |
Output is correct |
8 |
Correct |
80 ms |
1536 KB |
Output is correct |
9 |
Correct |
71 ms |
1612 KB |
Output is correct |
10 |
Correct |
66 ms |
1528 KB |
Output is correct |
11 |
Correct |
67 ms |
1532 KB |
Output is correct |
12 |
Correct |
70 ms |
1540 KB |
Output is correct |
13 |
Correct |
79 ms |
1528 KB |
Output is correct |
14 |
Correct |
69 ms |
1540 KB |
Output is correct |
15 |
Correct |
66 ms |
1520 KB |
Output is correct |
16 |
Correct |
67 ms |
1484 KB |
Output is correct |
17 |
Correct |
69 ms |
1524 KB |
Output is correct |
18 |
Correct |
66 ms |
1528 KB |
Output is correct |
19 |
Correct |
71 ms |
1524 KB |
Output is correct |
20 |
Correct |
71 ms |
1484 KB |
Output is correct |