QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22743 | #2365. Flight Collision | gsh# | TL | 3ms | 3716kb | C++20 | 1.6kb | 2022-03-10 15:56:43 | 2022-04-30 01:37:00 |
Judging History
answer
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define MAXN 100001
int N,x[MAXN],v[MAXN];bool vis[MAXN];
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
int main()
{
N=get();set<int>s;For(i,1,N)x[i]=get(),v[i]=get(),s.insert(i);
priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>>q;
For(i,2,N)
{
int k1=v[i],b1=x[i],k2=v[i-1],b2=x[i-1];
double t=k1!=k2?1.0*(b1-b2)/(k2-k1):1e18;if(t<0)continue;q.push({t,{i-1,i}});
}
while(!q.empty())
{
auto u=q.top().second;q.pop();int a=u.first,b=u.second;
if(vis[a]&&vis[b])continue;
if(!vis[a]&&!vis[b])
{
if(v[a]!=v[b])vis[a]=vis[b]=1,s.erase(a),s.erase(b);
auto t=s.lower_bound(a);bool flag=1;if(t!=s.begin())t--;else flag=0;
auto tt=s.upper_bound(b);if(tt==s.end())flag=0;
if(flag){int x=*t,y=*tt;double t=v[x]!=v[y]?1.0*(::x[x]-::x[y])/(v[y]-v[x]):1e18;if(t<0)continue;q.push({t,{x,y}});}continue;
}
if(vis[a])swap(a,b);auto tmp=s.lower_bound(a);
if(tmp!=s.begin()){auto t=tmp;t--;int c=*t;int k=v[a]-v[c],b=x[c]-x[a];if(!k)continue;if(1.0*b/k<0)continue;q.push({1.0*b/k,{c,a}});}
tmp++;if(tmp!=s.end()){int c=*tmp;int k=v[a]-v[c],b=x[c]-x[a];if(!k)continue;if(1.0*b/k<0)continue;q.push({1.0*b/k,{c,a}});}
}
cout<<s.size()<<'\n';for(auto i:s)cout<<i<<' ';return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3628kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3716kb
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: 3ms
memory: 3704kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 3612kb
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: 3ms
memory: 3700kb
input:
5 10 0 20 0 30 1 40 0 50 0
output:
3 1 2 5
result:
ok 2 lines
Test #7:
score: -100
Time Limit Exceeded
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 -...