QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87255 | #2365. Flight Collision | tovarisch | WA | 2ms | 3524kb | C++ | 2.0kb | 2023-03-12 06:55:40 | 2023-03-12 06:55:42 |
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];
bool wt[maxn];
set <int> in;
struct item {
long long da, dv;
int i, j;
bool operator > (const item& b) const {
return da * b.dv > b.da * dv;
}
};
priority_queue <item, vector <item>, greater<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.push(find(i, i + 1));
wt[i] = wt[i + 1] = 1;
}
}
while (!q.empty()) {
item u = q.top(); q.pop();
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 && !wt[l] && !wt[r] && check(l, r)){
q.push(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: 3332kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3364kb
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: 3476kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3524kb
input:
9 10 10 20 7 30 5 40 0 42 0 50 -1 60 -2 70 -10 80 -12
output:
1 9
result:
wrong answer 2nd lines differ - expected: '1', found: '9'