QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22851#2365. Flight CollisionDaBenZhongXiaSongKuaiDi#WA 3ms3828kbC++201.1kb2022-03-10 18:25:092022-04-30 01:47:58

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:47:58]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3828kb
  • [2022-03-10 18:25:09]
  • 提交

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'