QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22734#2365. Flight Collisionhy_zheng_zai_nei_juan#WA 5ms7760kbC++202.4kb2022-03-10 15:48:052022-04-30 01:36:38

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:36:38]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:7760kb
  • [2022-03-10 15:48:05]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
    #define BUF_SIZE 100000
    bool IOerror=0;
    inline char nc()
	{
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline ll read()
	{
        bool sign=0; char ch=nc();ll x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return 0;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
        return x;
    }
    #undef BUF_SIZE
};
using namespace fastIO;
int x[1000010],v[1000010];
struct node
{
	int x,y;
};
set<int>s;
int calc(node a)
{
	if(v[a.x]<=v[a.y])return 1e16;
	return 1.0*(x[a.y]-x[a.x])/(v[a.x]-v[a.y]);
}
bool operator < (const node& a,const node& b)
{
	return calc(a)>calc(b);
}
vector<int>ans;
int crash[1000010];
priority_queue<node>q;
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n=qr;
	for(int i=1;i<=n;i++)in(x[i]),in(v[i]),s.insert(i);
	for(int i=1;i<n;i++)
	{
		q.push((node){i,i+1});
	}
	while(!q.empty())
	{
		node now=q.top();q.pop();
		// cout<<now.x<<','<<now.y<<'\n';
		if(calc(now)>1e15)break;
		if(!(crash[now.x]&&crash[now.y]))
		{
			if(crash[now.y])
			{
				auto suf=s.lower_bound(now.y);
				if(suf!=s.end())q.push((node){now.x,*suf});
			}
			else if(crash[now.x])
			{
				auto pre=s.lower_bound(now.x);
				if(pre!=s.begin())q.push((node){*--pre,now.y});
			}
			else
			{
				crash[now.x]=crash[now.y]=1;
				s.erase(now.x),s.erase(now.y);
				auto pre=s.lower_bound(now.x);
				auto suf=s.lower_bound(now.y);
				if(pre!=s.begin()&&suf!=s.end())q.push((node){*--pre,*suf});
			}
		}
	}
	for(int i=1;i<=n;i++)if(!crash[i])ans.push_back(i);
	cout<<ans.size()<<'\n';
	for(auto i:ans)cout<<i<<' ';
	return 0;
}

详细

Test #1:

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

input:

1
-4 13

output:

1
1 

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 5ms
memory: 7684kb

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: 7676kb

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3 

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 7688kb

input:

2
5 4
10 5

output:

2
1 2 

result:

ok 2 lines

Test #5:

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

input:

9
10 10
20 7
30 5
40 0
42 0
50 -1
60 -2
70 -10
80 -12

output:

1
5 

result:

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