QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22743#2365. Flight Collisiongsh#TL 3ms3716kbC++201.6kb2022-03-10 15:56:432022-04-30 01:37:00

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:37:00]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:3716kb
  • [2022-03-10 15:56:43]
  • 提交

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 -...

output:


result: