#include<bits/stdc++.h>
#include <rail.h>
using namespace std;
int getDistance(int i, int j);//{
// cout << i << ' ' << j << '\n';
// int r;
// cin >> r;
// return r;
// }
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
if(n == 1) return;
int d0[n], o[n], d1[n], o1[n], ind = 1;
d0[0] = 0;
for(int i = 1;i < n;i++) {
d0[i] = getDistance(0, i);
o[i-1] = i;
}
sort(o, o+n-1, [&d0](int a, int b){
return d0[a] < d0[b];
});
int s = o[0];
stype[s] = 2;
location[s] = first+d0[s];
d1[0] = d0[s];
o1[0] = 0;
d1[s] = 0;
for(int i = 1;i < n;i++){
if(i == s) continue;
o1[ind++] = i;
d1[i] = getDistance(s, i);
}
sort(o1, o1+ind, [&d1](int a, int b){return d1[a] < d1[b];});
int l2 = s;
set<int> s2;
s2.insert(location[s]);
for(int z = 1;z < n-1;z++){
int i = o[z];
if(d0[i] == d0[s]+d1[i]) continue;
int g = getDistance(l2, i);
int hp = location[l2]-g;
int ll2 = *s2.lower_bound(hp+1);
if(d0[i] != ll2-first+ll2-hp){
l2 = i;
location[i] = first+d0[i];
stype[i] = 2;
s2.insert(location[i]);
} else {
stype[i] = 1;
location[i] = location[l2]-g;
}
}
l2 = -1;
first = location[s];
s2.clear();
for(int z = 0;z < ind;z++){
int i = o1[z];
if(!i){
l2 = i;
s2.insert(0);
continue;
}
if(d0[i] < d0[s]+d1[i]) continue;
if(l2 == -1){
stype[i] = 1;
location[i] = first-d1[i];
l2 = i;
s2.insert(location[i]);
continue;
}
int g = getDistance(l2, i);
int hp = location[l2]+g;
int ll2 = *prev(s2.lower_bound(hp));
if(d1[i] != first-ll2+hp-ll2){
l2 = i;
location[i] = first-d1[i];
stype[i] = 1;
s2.insert(location[i]);
} else {
stype[i] = 2;
location[i] = location[l2]+g;
}
}
}
// int main(){
// int loc[8], typ[8];
// findLocation(8, 4, loc, typ);
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
5 ms |
276 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
376 KB |
Output is correct |
3 |
Correct |
1 ms |
340 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 |
384 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 |
388 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
596 KB |
Output is correct |
2 |
Correct |
45 ms |
644 KB |
Output is correct |
3 |
Correct |
45 ms |
640 KB |
Output is correct |
4 |
Correct |
45 ms |
588 KB |
Output is correct |
5 |
Correct |
44 ms |
628 KB |
Output is correct |
6 |
Correct |
44 ms |
636 KB |
Output is correct |
7 |
Correct |
46 ms |
624 KB |
Output is correct |
8 |
Correct |
44 ms |
628 KB |
Output is correct |
9 |
Correct |
44 ms |
624 KB |
Output is correct |
10 |
Correct |
45 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
528 KB |
Output is correct |
2 |
Correct |
49 ms |
624 KB |
Output is correct |
3 |
Correct |
48 ms |
632 KB |
Output is correct |
4 |
Correct |
51 ms |
512 KB |
Output is correct |
5 |
Correct |
49 ms |
636 KB |
Output is correct |
6 |
Correct |
45 ms |
588 KB |
Output is correct |
7 |
Correct |
50 ms |
632 KB |
Output is correct |
8 |
Correct |
45 ms |
624 KB |
Output is correct |
9 |
Correct |
46 ms |
640 KB |
Output is correct |
10 |
Correct |
45 ms |
588 KB |
Output is correct |
11 |
Correct |
44 ms |
624 KB |
Output is correct |
12 |
Correct |
45 ms |
624 KB |
Output is correct |
13 |
Correct |
45 ms |
636 KB |
Output is correct |
14 |
Correct |
45 ms |
628 KB |
Output is correct |
15 |
Correct |
46 ms |
588 KB |
Output is correct |
16 |
Correct |
45 ms |
644 KB |
Output is correct |
17 |
Correct |
44 ms |
640 KB |
Output is correct |
18 |
Correct |
44 ms |
588 KB |
Output is correct |
19 |
Correct |
45 ms |
640 KB |
Output is correct |
20 |
Correct |
45 ms |
640 KB |
Output is correct |