QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22679#2365. Flight CollisionMr_Eight#WA 2ms3664kbC++202.7kb2022-03-10 15:18:102022-04-30 01:32:05

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:05]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3664kb
  • [2022-03-10 15:18:10]
  • 提交

answer

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x) {
		if(x==0){
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x ,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
ll n,x[100002],v[100002];
set<int>res;
bool vis[100002];
typedef pair<double,pair<int,int> > S;
priority_queue<S,vector<S>,greater<S> >q;
inline void ck(int xx,int y){
	if(v[xx]>v[y]&&xx&&y<=n)q.push(make_pair((x[y]-x[xx])*1.0L/(v[xx]-v[y]),make_pair(xx,y)));
}
int main() {
	cin>>n;
	F(i,1,n)read(x[i],v[i]),res.insert(i);
	F(i,1,n-1)ck(i,i+1);
	res.insert(0);res.insert(n+1);
	while(!q.empty()){
		auto s=q.top();q.pop();
		int a=s.second.first,b=s.second.second;
		if(vis[a]||vis[b])continue;
		vis[a]=vis[b]=true;
		int pre=*--res.lower_bound(a),suf=*res.upper_bound(b);
		res.erase(a);res.erase(b);
		ck(pre,suf);
	}
	write(res.size()-2,'\n');
	for(auto i:res)if(i&&i<=n)write(i,'\n');
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3468kb

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3664kb

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: 2ms
memory: 3584kb

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3

result:

ok 2 lines

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3536kb

input:

2
5 4
10 5

output:

2
1
2

result:

wrong answer 2nd lines differ - expected: '1 2', found: '1'