QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22679 | #2365. Flight Collision | Mr_Eight# | WA | 2ms | 3664kb | C++20 | 2.7kb | 2022-03-10 15:18:10 | 2022-04-30 01:32:05 |
Judging History
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'