QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87257 | #2365. Flight Collision | tovarisch | TL | 109ms | 12696kb | C++ | 2.0kb | 2023-03-12 06:58:37 | 2023-03-12 06:58:37 |
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 <pii, pii>;
const int maxn = 1e5 + 10;
int n;
int a[maxn], v[maxn];
set <int> in;
struct item {
long long da, dv;
int i, j;
bool operator < (const item& b) const {
if (da * b.dv == b.da * dv) {
if (i == b.i) return j < b.j;
return i < b.i;
}
return da * b.dv < b.da * dv;
}
};
set <item> q;
bool check(int i, int j) {
if (i > j) swap(i, j);
return v[i] > v[j];
}
item find(int i, int j) {
if (i > j) swap(i, j);
long long da = a[i] - a[j], dv = v[j] - v[i];
return {da, dv, i, j};
}
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.insert(find(i, i + 1));
}
}
while (!q.empty()) {
item u = *q.begin(); q.erase(q.begin());
int i = u.i, j = u.j;
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.insert(find(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: 3408kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3332kb
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: 3360kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3520kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 3548kb
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: 2ms
memory: 3304kb
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: 37ms
memory: 8764kb
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: 56ms
memory: 11976kb
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: 48ms
memory: 11948kb
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: 50ms
memory: 11944kb
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: 109ms
memory: 12696kb
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: 48ms
memory: 8812kb
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: 44ms
memory: 8824kb
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: 2ms
memory: 3548kb
input:
2 -1000000000 1000000000 1000000000 1000000000
output:
2 1 2
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 3480kb
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