QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22665#2365. Flight Collisionasoul#WA 4ms9936kbC++141.2kb2022-03-10 15:09:042022-04-30 01:30:53

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:30:53]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9936kb
  • [2022-03-10 15:09:04]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;

const int maxn=3e5;

int n;
ll X[maxn+5],v[maxn+5]; 
vector<int> ans; 
struct node {
	int x,y; 
	ll p,q; 
	bool operator < (const node &x) const {
		if (x.q==0) return 1;
		if (q==0) return 0; 
		return p*x.q<q*x.p;
	}
} ; 
node make(int x,int y) {
	ll p=(X[y]-X[x]),q=(v[x]-v[y]);
	node ret; 
	ret.x=x,ret.y=y; 
	ret.p=p,ret.q=q;
	return ret;
}
set<node> T; 
int vis[maxn+5],nxt[maxn+5],lst[maxn+5]; 
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%lld %lld",&X[i],&v[i]); 
		if (i!=n) nxt[i]=i+1;
		if (i!=1) lst[i]=i-1;
	}
	for (int i=1;i<n;i++) {
		T.insert(make(i,i+1));
	}
	for (int i=1;i<=n;i++) {
		if (T.size()==0) break ; 
		node t=*T.begin(); 
		if (t.q==0) break ;
		if (t.x>t.y) swap(t.x,t.y); 
		int ls=lst[t.x],nx=nxt[t.y];
		if (ls!=0) nxt[ls]=nx;
		if (nx!=0) lst[nx]=ls;
		if (ls!=0 && nx!=0) T.insert(make(ls,nx));  
		vis[t.x]=vis[t.y]=1; 
	}
	for (int i=1;i<=n;i++) {
		if (!vis[i]) ans.push_back(i); 
	}
	printf("%d\n",ans.size());
	for (auto x:ans) printf("%d ",x); 
 	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 7864kb

input:

1
-4 13

output:

1
1 

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 9936kb

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'