QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22851 | #2365. Flight Collision | DaBenZhongXiaSongKuaiDi# | WA | 3ms | 3828kb | C++20 | 1.1kb | 2022-03-10 18:25:09 | 2022-04-30 01:47:58 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<db,pair<int,int>>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
//d * n = s * k + remain
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
const int maxn = 1e5 + 5;
int x[maxn],v[maxn];
priority_queue<pii> Q;
void add(int p,int q){
if(v[p] <= v[q]) return;
db T = (db)(x[p] - x[q]) / (db)(v[p] - v[q]);
Q.push(make_pair(T,make_pair(p,q)));
}
int main(){
set<int> s;
int n = rd();
for(int i = 1;i <= n;i++){
x[i] = rd();
v[i] = rd();
s.insert(i);
}
for(int i = 1;i < n;i++)
add(i,i + 1);
while(!Q.empty() && s.size()){
auto P = Q.top().se;
int i = P.fi;
int j = P.se;
Q.pop();
if(!s.count(j) || !s.count(i)) continue;
s.erase(i);
s.erase(j);
if(!s.size()) break;
auto it = s.lower_bound(i);
if(it == s.end() || it == s.begin()) continue;
int pre = *(--it);
int nxt = *s.lower_bound(j);
add(pre,nxt);
}
printf("%d\n",s.size());
for(auto it:s){
cout << it << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3788kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 3816kb
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: 3828kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 3824kb
input:
2 5 4 10 5
output:
2 1 2
result:
wrong answer 2nd lines differ - expected: '1 2', found: '1'