QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87253 | #2365. Flight Collision | tovarisch | TL | 95ms | 10632kb | C++ | 1.8kb | 2023-03-12 06:43:56 | 2023-03-12 06:43:59 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <iomanip>
using namespace std;
/* *
*
* Too many mind, no mind.
*
* */
using pii = pair <int, int>;
using pdi = pair <long double, pii>;
const int maxn = 1e5 + 10;
int n;
int a[maxn], v[maxn];
set <int> in;
priority_queue <pdi, vector <pdi>, greater<pdi>> q;
bool check(int i, int j) {
if (i > j) swap(i, j);
return v[i] > v[j];
}
long double find(int i, int j) {
if (i > j) swap(i, j);
long double x = a[i] - a[j], y = v[j] - v[i];
return x / y;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i] >> v[i];
for (int i = 0; i < n; i++) in.insert(i);
for (int i = 0; i + 1 < n; i++) {
if (check(i, i + 1)) {
q.push({find(i, i + 1), {i, i + 1}});
}
}
while (!q.empty()) {
pdi u = q.top(); q.pop();
int i = u.second.first, j = u.second.second;
if (i > j) swap(i, j);
if (in.count(i) && in.count(j)) {
in.erase(i);
in.erase(j);
int l = -1, r = -1;
auto it = in.lower_bound(i);
if (it != in.begin()) {
it--;
l = *it;
}
it = in.upper_bound(j);
if (it != in.end()) r = *it;
if (l != -1 && r != -1 && check(l, r)){
q.push({find(l, r), {l, r}});
}
}
}
cout << in.size() << endl;
auto it = in.begin();
cout << *it + 1;
it++;
while (it != in.end()) {
cout << " " << *it + 1;
it++;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3360kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
5 1 1000000000 2 1000000000 3 -1000000000 4 -1000000000 5 -1000000000
output:
1 5
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 3ms
memory: 3376kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
9 10 10 20 7 30 5 40 0 42 0 50 -1 60 -2 70 -10 80 -12
output:
1 1
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 4ms
memory: 3396kb
input:
5 10 0 20 0 30 1 40 0 50 0
output:
3 1 2 5
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 39ms
memory: 8956kb
input:
98765 0 -48539 1 -48539 2 -48539 3 -48539 4 -48539 5 -48539 6 -48539 7 -48539 8 -48539 9 -48539 10 -48539 11 -48539 12 -48539 13 -48539 14 -48539 15 -48539 16 -48539 17 -48539 18 -48539 19 -48539 20 -48539 21 -48539 22 -48539 23 -48539 24 -48539 25 -48539 26 -48539 27 -48539 28 -48539 29 -48539 30 -...
output:
98765 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 58ms
memory: 10632kb
input:
99999 -999999396 999999395 -999971669 999999396 -999971668 -999999396 -999961260 999999396 -999961259 -999999396 -999907239 999999396 -999907238 -999999396 -999754561 999999396 -999754560 -999999396 -999662011 999999396 -999662010 -999999396 -999651505 999999396 -999651504 -999999396 -999619141 9999...
output:
1 99999
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 62ms
memory: 10588kb
input:
99999 -999999244 999999243 -999956299 999999244 -999956298 -999999244 -999945616 999999244 -999945615 -999999244 -999944410 999999244 -999944409 -999999244 -999891030 999999244 -999891029 -999999244 -999862261 999999244 -999862260 -999999244 -999835376 999999244 -999835375 -999999244 -999705681 9999...
output:
1 1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 68ms
memory: 10632kb
input:
99999 -999999634 999999633 -999951510 999999634 -999951509 -999999634 -999895803 999999634 -999895802 -999999634 -999883648 999999634 -999883647 -999999634 -999880002 999999634 -999880001 -999999634 -999879250 999999634 -999879249 -999999634 -999758480 999999634 -999758479 -999999634 -999583344 9999...
output:
1 1
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 95ms
memory: 10572kb
input:
100000 0 0 1 -499999669 2 -999999337 1000 999998221 1001 499999611 1002 1000 2000 2000 2001 -499998575 2002 -999999149 3000 999999419 3001 500001210 3002 3000 4000 4000 4001 -499997324 4002 -999998647 5000 5000 6000 999998787 6001 500002394 6002 6000 7000 7000 8000 8000 9000 9000 9001 -249992975 900...
output:
5702 3 16 21 46 47 76 77 78 79 102 103 118 123 124 151 152 153 174 189 194 243 266 267 298 299 304 309 310 319 324 325 326 351 396 397 506 507 542 551 556 571 572 629 638 649 650 665 764 807 832 837 876 921 938 959 976 977 978 1167 1220 1221 1228 1237 1238 1273 1280 1285 1290 1291 1292 1293 1370 137...
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 34ms
memory: 8936kb
input:
99999 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1...
output:
1 1
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 35ms
memory: 9012kb
input:
100000 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 ...
output:
2 1 2
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
2 -1000000000 1000000000 1000000000 1000000000
output:
2 1 2
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
2 -1000000000 999999999 1000000000 1000000000
output:
2 1 2
result:
ok 2 lines
Test #16:
score: -100
Time Limit Exceeded
input:
2 -1000000000 1000000000 1000000000 999999999
output:
0