QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87250 | #2365. Flight Collision | tovarisch | WA | 73ms | 11728kb | C++ | 2.3kb | 2023-03-12 06:38:07 | 2023-03-12 06:38:10 |
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 <double, pii>;
const int maxn = 1e5 + 10;
int n;
int a[maxn], v[maxn];
set <int> in;
set <pii> comp;
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];
}
double find(int i, int j) {
if (i > j) swap(i, j);
return double(a[i] - a[j]) / double(v[j] - v[i]);
}
void match(int i) {
auto it = in.upper_bound(i);
if (it != in.end()) {
int j = *it;
if (check(i, j)) {
if (!comp.count({i, j})) {
q.push({find(i, j), {i, j}});
comp.insert({i, j});
}
}
}
it = in.lower_bound(i);
if (it != in.begin()) {
it--;
int j = *it;
if (check(j, i)) {
if (!comp.count({i, j})) {
q.push({find(j, i), {j, i}});
comp.insert({i, j});
}
}
}
}
void add(int i) {
auto it = in.upper_bound(i);
if (it != in.end()) match(*it);
it = in.lower_bound(i);
if (it != in.begin()) {
it--;
match(*it);
}
}
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}});
comp.insert({i, i + 1});
}
}
while (!q.empty()) {
pdi u = q.top(); q.pop();
int i = u.second.first, j = u.second.second;
comp.erase({i, j});
if (in.count(i) && in.count(j)) {
in.erase(i);
in.erase(j);
add(i);
add(j);
} else if (in.count(i)) {
match(i);
add(j);
} else if (in.count(j)){
match(j);
add(i);
} else {
add(i);
add(j);
}
}
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: 0ms
memory: 3364kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3400kb
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: 0ms
memory: 3396kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3404kb
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: 1ms
memory: 3404kb
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: 8936kb
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: 73ms
memory: 11640kb
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: -100
Wrong Answer
time: 51ms
memory: 11728kb
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 99999
result:
wrong answer 2nd lines differ - expected: '1', found: '99999'