QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22696#2365. Flight Collisiongsh#WA 2ms3648kbC++201.3kb2022-03-10 15:29:072022-04-30 01:32:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:32:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3648kb
  • [2022-03-10 15:29:07]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'