QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22696 | #2365. Flight Collision | gsh# | WA | 2ms | 3648kb | C++20 | 1.3kb | 2022-03-10 15:29:07 | 2022-04-30 01:32:56 |
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];if(k1==k2)continue;
double t=1.0*(b1-b2)/(k2-k1);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]){vis[a]=vis[b]=1,s.erase(a),s.erase(b);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;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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3648kb
input:
5 1 1000000000 2 1000000000 3 -1000000000 4 -1000000000 5 -1000000000
output:
3 1 4 5
result:
wrong answer 1st lines differ - expected: '1', found: '3'