QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22794#2365. Flight CollisionQyc_AK_NOI2022#AC ✓94ms10980kbC++146.1kb2022-03-10 16:40:212022-04-30 01:40:49

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:40:49]
  • 评测
  • 测评结果:AC
  • 用时:94ms
  • 内存:10980kb
  • [2022-03-10 16:40:21]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
#define double long double
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<double,std::pair<int,int> > pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
    #define BUF_SIZE (1<<16)
    #define OUT_SIZE (1<<16)
    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)return IOerror=1,-1;}return *p1++;}
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
        inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(int x){print(x);out('\n');}
        inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(ll x){print(x);out('\n');}
        inline void print(double x,int y){//y<18
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
        }
        inline void println(double x,int y){print(x,y);out('\n');}
        inline void print(char *s){while(*s)out(*s++);}
        inline void println(char *s){while(*s)out(*s++);out('\n');}
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef OUT_SIZE
    #undef BUF_SIZE
}using namespace IO;
namespace Little_function{
	inline int abs(int x){return x<0?-x:x;}
	inline ll abs(ll x){return x<0?-x:x;}
	inline double abs(double x){return x<0?-x:x;}
	inline int max(const int &a,const int &b){return a>b?a:b;}
	inline ll max(const ll &a,const ll &b){return a>b?a:b;}
	inline double max(const double &a,const double &b){return a>b?a:b;}
	inline int min(const int &a,const int &b){return a<b?a:b;}
	inline ll min(const ll &a,const ll &b){return a<b?a:b;}
	inline double min(const double &a,const double &b){return a<b?a:b;}
	inline void swap(int &x,int &y){x^=y^=x^=y;}
	inline void swap(ll &x,ll &y){x^=y^=x^=y;}
	inline void swap(double &x,double &y){double t=x;x=y,y=t;}
	inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
	inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
	int gcd(int a,int b){return !b?a:gcd(b,a%b);}
	ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
const int N=2e5+13;
int n;
struct Node{int x,v;}a[N];
std::priority_queue<pii> q;
std::set<int> t;
inline void add(int u,int v){
	if(a[u].v<=a[v].v) return;
	q.push(mp((double)(a[u].x-a[v].x)/(double)(a[u].v-a[v].v),mp(u,v)));
}
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(a[i].x),read(a[i].v);
	for(int i=1;i<=n;++i) t.insert(i);
	for(int i=2;i<=n;++i) add(i-1,i);
	int sum=n;
	while(!q.empty()){
		std::pair<int,int> x=q.top().se;q.pop();
		if(t.find(x.fi)==t.end()||t.find(x.se)==t.end()) continue;
		t.erase(x.fi),t.erase(x.se);
		std::set<int>::iterator it1=t.lower_bound(x.fi),it2=t.lower_bound(x.se);
		if(it1!=t.begin()&&it2!=t.end()) add(*(--it1),*it2);
		sum-=2;
	}
	println(sum);
	for(std::set<int>::iterator it=t.begin();it!=t.end();++it) print(*it),print(' ');
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3736kb

input:

1
-4 13

output:

1
1 

result:

ok 2 lines

Test #2:

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

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3 

result:

ok 2 lines

Test #4:

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

input:

2
5 4
10 5

output:

2
1 2 

result:

ok 2 lines

Test #5:

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

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

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: 29ms
memory: 9128kb

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: 43ms
memory: 10844kb

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: 0
Accepted
time: 43ms
memory: 10776kb

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
1 

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 48ms
memory: 10840kb

input:

99999
-999999634 999999633
-999951510 999999634
-999951509 -999999634
-999895803 999999634
-999895802 -999999634
-999883648 999999634
-999883647 -999999634
-999880002 999999634
-999880001 -999999634
-999879250 999999634
-999879249 -999999634
-999758480 999999634
-999758479 -999999634
-999583344 9999...

output:

1
1 

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 70ms
memory: 10760kb

input:

100000
0 0
1 -499999669
2 -999999337
1000 999998221
1001 499999611
1002 1000
2000 2000
2001 -499998575
2002 -999999149
3000 999999419
3001 500001210
3002 3000
4000 4000
4001 -499997324
4002 -999998647
5000 5000
6000 999998787
6001 500002394
6002 6000
7000 7000
8000 8000
9000 9000
9001 -249992975
900...

output:

5702
3 16 21 46 47 76 77 78 79 102 103 118 123 124 151 152 153 174 189 194 243 266 267 298 299 304 309 310 319 324 325 326 351 396 397 506 507 542 551 556 571 572 629 638 649 650 665 764 807 832 837 876 921 938 959 976 977 978 1167 1220 1221 1228 1237 1238 1273 1280 1285 1290 1291 1292 1293 1370 137...

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 26ms
memory: 9192kb

input:

99999
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
50 1
51 1
52 1
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60 1...

output:

1
1 

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 27ms
memory: 9220kb

input:

100000
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
50 1
51 1
52 1
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60 ...

output:

2
1 2 

result:

ok 2 lines

Test #14:

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

input:

2
-1000000000 1000000000
1000000000 1000000000

output:

2
1 2 

result:

ok 2 lines

Test #15:

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

input:

2
-1000000000 999999999
1000000000 1000000000

output:

2
1 2 

result:

ok 2 lines

Test #16:

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

input:

2
-1000000000 1000000000
1000000000 999999999

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2
-1000000000 999999999
1000000000 999999999

output:

2
1 2 

result:

ok 2 lines

Test #18:

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

input:

10
-8 1
-4 1
-3 3
-2 -9
2 -3
4 1
5 1
6 4
8 4
10 3

output:

4
1 6 7 8 

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 90ms
memory: 10980kb

input:

100000
-999990163 -377895309
-999984163 8973261
-999979867 834504530
-999953994 761228981
-999936881 -463878169
-999916723 -15264200
-999907073 -174466667
-999877240 -726147638
-999876260 947109625
-999846455 -153928844
-999842048 -820363438
-999816282 549455586
-999814709 990129
-999808106 -5103181...

output:

8
1 2448 60523 62076 62079 74424 99893 99998 

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 82ms
memory: 10816kb

input:

100000
-999999527 -897350344
-999982057 -849659915
-999973845 -76432407
-999947168 295353679
-999944429 -291836812
-999943207 -113638209
-999929091 277369081
-999923482 -341494644
-999901773 -413159641
-999886430 386321890
-999873068 -832012113
-999863798 296432997
-999856998 -228698165
-999794684 -...

output:

6
1 2 62119 89002 99727 99998 

result:

ok 2 lines

Test #21:

score: 0
Accepted
time: 91ms
memory: 10764kb

input:

100000
-999970270 -507664063
-999953025 -779973700
-999951134 768353813
-999942782 256251065
-999923116 -331605753
-999915433 -78154988
-999907734 631563655
-999907262 -335053550
-999901832 -846942814
-999899573 -790177737
-999889186 838524268
-999873298 -730637168
-999870040 677208179
-999858626 95...

output:

6
72943 83560 99261 99330 99951 99952 

result:

ok 2 lines

Test #22:

score: 0
Accepted
time: 94ms
memory: 10776kb

input:

100000
-999999663 606420568
-999977713 -465238391
-999972974 -470545763
-999922236 587581803
-999917815 -352443486
-999910614 -151519504
-999903937 230521617
-999880664 473948012
-999879036 533852278
-999846934 -277893200
-999844515 -825287819
-999838091 -647654324
-999824249 545274926
-999805576 -7...

output:

4
3 120 1729 12556 

result:

ok 2 lines

Test #23:

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

input:

2
3 -8
4 10

output:

2
1 2 

result:

ok 2 lines

Test #24:

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

input:

2
-57 23
91 11

output:

0

result:

ok single line: '0'

Test #25:

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

input:

10
-926 345
-872 -566
-680 465
-348 -50
-71 -500
16 939
402 -386
592 -709
617 -515
713 -824

output:

0

result:

ok single line: '0'

Test #26:

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

input:

23
-9789 6740
-9087 7154
-8243 3939
-6908 9254
-6829 -426
-6367 1462
-3319 -2522
-2438 4232
-1161 -2195
-305 3393
2357 -9935
2571 -2348
3537 6328
4256 6094
7195 -2556
7315 6805
7359 -355
8361 9027
8532 -4742
8792 7705
9083 2738
9142 -9725
9242 6364

output:

3
7 12 13 

result:

ok 2 lines

Test #27:

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

input:

223
-210 92
-208 -103
-205 153
-204 110
-203 165
-197 -147
-196 -70
-195 -93
-194 61
-193 -158
-192 54
-188 -108
-187 -14
-186 -128
-185 -86
-183 -157
-182 146
-178 183
-177 62
-170 135
-166 56
-162 63
-161 180
-160 -37
-159 210
-158 -140
-157 166
-156 12
-155 204
-152 30
-148 -147
-146 113
-141 6
-...

output:

3
189 194 197 

result:

ok 2 lines

Test #28:

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

input:

1002
-100179 -21171
-99945 41039
-99874 55638
-99733 71524
-99523 67610
-99143 -35927
-98730 27793
-98540 85922
-98521 35885
-98492 44007
-98361 49124
-97803 -94904
-97591 -83195
-97569 11766
-97151 -13511
-97073 -89473
-96949 -24584
-96945 88291
-96487 11795
-96406 14793
-96393 -74765
-96348 -65018...

output:

2
157 164 

result:

ok 2 lines

Test #29:

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

input:

102
-51 28
-50 -43
-49 10
-48 1
-47 35
-46 48
-45 -13
-44 -31
-43 47
-42 -33
-41 -4
-40 2
-39 -19
-38 30
-37 9
-36 7
-35 6
-34 0
-32 -10
-31 -20
-30 -49
-29 25
-28 -20
-27 -44
-26 39
-25 0
-24 47
-23 21
-22 44
-21 29
-20 10
-19 12
-18 -18
-17 -15
-16 22
-15 48
-14 16
-13 9
-12 -5
-11 -9
-10 -39
-9 1...

output:

2
11 16 

result:

ok 2 lines

Test #30:

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

input:

10023
-43847833 25247568
-43845663 8733039
-43838636 5179259
-43836292 1793827
-43822381 40024163
-43820210 -39007118
-43817905 -2879971
-43815454 -30954405
-43815166 -5172304
-43812716 -33955692
-43802254 39807831
-43786912 37254277
-43781753 -23294796
-43781248 -43787269
-43777151 -7784632
-437602...

output:

3
31 292 293 

result:

ok 2 lines

Test #31:

score: 0
Accepted
time: 81ms
memory: 10836kb

input:

100000
-50000 24770
-49999 20894
-49998 13386
-49997 18436
-49996 5532
-49995 46989
-49994 -47019
-49993 5933
-49992 25157
-49991 38760
-49990 -18838
-49989 -26564
-49988 13720
-49987 -20401
-49986 -25596
-49985 -17766
-49984 -40566
-49983 -4333
-49982 -8765
-49981 -4272
-49980 -33122
-49979 -49859
...

output:

6
7379 7380 7381 7396 96725 99984 

result:

ok 2 lines

Test #32:

score: 0
Accepted
time: 89ms
memory: 10704kb

input:

100000
-50010 38174
-50009 6226
-50008 -45668
-50007 -28702
-50006 -43951
-50005 38612
-50004 -10089
-50003 36228
-50002 3152
-50001 -31933
-50000 -11085
-49999 -16941
-49998 37111
-49997 -26162
-49996 -43943
-49995 39192
-49994 10898
-49993 -44560
-49992 5905
-49991 34476
-49990 -24532
-49989 28474...

output:

4
5 37240 37957 99998 

result:

ok 2 lines

Test #33:

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

input:

100
-51 -12
-50 -40
-48 -44
-47 39
-46 -24
-45 -45
-44 28
-43 -50
-42 13
-41 23
-40 -25
-39 42
-38 19
-37 26
-36 -17
-35 46
-34 -24
-33 35
-32 47
-31 27
-30 -10
-29 -17
-28 -46
-27 31
-26 -31
-25 -48
-24 20
-23 31
-22 -16
-21 -21
-20 -23
-19 -29
-18 11
-17 51
-16 9
-15 -43
-14 -44
-12 -41
-11 10
-10...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 77ms
memory: 9800kb

input:

83382
-133993820 76865248
-133990261 7033984
-133985576 131479163
-133983908 77729895
-133982156 -106523218
-133976468 12730762
-133975243 132782745
-133972485 -35728865
-133971240 42445369
-133968182 18266933
-133958226 -12176455
-133954836 -88478665
-133952445 10482634
-133951610 1798923
-13395084...

output:

8
21 268 2027 2114 73043 81406 83355 83358 

result:

ok 2 lines