QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22755#2365. Flight Collisionhy_zheng_zai_nei_juan#WA 69ms17396kbC++202.5kb2022-03-10 16:04:062022-04-30 01:37:51

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:37:51]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:17396kb
  • [2022-03-10 16:04:06]
  • 提交

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;
long double 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<<' '<<calc(now)<<'\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: 2ms
memory: 7784kb

input:

1
-4 13

output:

1
1 

result:

ok 2 lines

Test #2:

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

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3 

result:

ok 2 lines

Test #4:

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

input:

2
5 4
10 5

output:

2
1 2 

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 7696kb

input:

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

output:

1
1 

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 3ms
memory: 7772kb

input:

5
10 0
20 0
30 1
40 0
50 0

output:

3
1 2 5 

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 28ms
memory: 17396kb

input:

98765
0 -48539
1 -48539
2 -48539
3 -48539
4 -48539
5 -48539
6 -48539
7 -48539
8 -48539
9 -48539
10 -48539
11 -48539
12 -48539
13 -48539
14 -48539
15 -48539
16 -48539
17 -48539
18 -48539
19 -48539
20 -48539
21 -48539
22 -48539
23 -48539
24 -48539
25 -48539
26 -48539
27 -48539
28 -48539
29 -48539
30 -...

output:

98765
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 69ms
memory: 16396kb

input:

99999
-999999396 999999395
-999971669 999999396
-999971668 -999999396
-999961260 999999396
-999961259 -999999396
-999907239 999999396
-999907238 -999999396
-999754561 999999396
-999754560 -999999396
-999662011 999999396
-999662010 -999999396
-999651505 999999396
-999651504 -999999396
-999619141 9999...

output:

1
99999 

result:

ok 2 lines

Test #9:

score: -100
Wrong Answer
time: 57ms
memory: 14500kb

input:

99999
-999999244 999999243
-999956299 999999244
-999956298 -999999244
-999945616 999999244
-999945615 -999999244
-999944410 999999244
-999944409 -999999244
-999891030 999999244
-999891029 -999999244
-999862261 999999244
-999862260 -999999244
-999835376 999999244
-999835375 -999999244
-999705681 9999...

output:

1
99999 

result:

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