QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87253#2365. Flight CollisiontovarischTL 95ms10632kbC++1.8kb2023-03-12 06:43:562023-03-12 06:43:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-12 06:43:59]
  • 评测
  • 测评结果:TL
  • 用时:95ms
  • 内存:10632kb
  • [2023-03-12 06:43:56]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <iomanip>

using namespace std;
/* *
 *
 * Too many mind, no mind.
 *
 * */
using pii = pair <int, int>;
using pdi = pair <long double, pii>;
const int maxn = 1e5 + 10;
int n; 
int a[maxn], v[maxn];
set <int> in;
priority_queue <pdi, vector <pdi>, greater<pdi>> q;
bool check(int i, int j) {
	if (i > j) swap(i, j);
	return v[i] > v[j];
}
long double find(int i, int j) {
	if (i > j) swap(i, j);
	long double x = a[i] - a[j], y = v[j] - v[i];
	return x / y;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i] >> v[i];
	for (int i = 0; i < n; i++) in.insert(i);

	for (int i = 0; i + 1 < n; i++) {
		if (check(i, i + 1)) {
			q.push({find(i, i + 1), {i, i + 1}});
		}
	}

	while (!q.empty()) {
		pdi u = q.top(); q.pop();
		int i = u.second.first, j = u.second.second;
		if (i > j) swap(i, j);

		if (in.count(i) && in.count(j)) {
			in.erase(i);
			in.erase(j);
			int l = -1, r = -1;

			auto it = in.lower_bound(i);

			if (it != in.begin()) {
				it--;
				l = *it;
			}
			it = in.upper_bound(j);
			if (it != in.end()) r = *it;
			if (l != -1 && r != -1 && check(l, r)){
				q.push({find(l, r), {l, r}});
			}
		} 
	}

	cout << in.size() << endl;
	auto it = in.begin();
	cout << *it + 1;
	it++;
	while (it != in.end()) {
		cout << " " << *it + 1;
		it++;
	}
	return 0;
}

详细

Test #1:

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

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

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

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3

result:

ok 2 lines

Test #4:

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

input:

2
5 4
10 5

output:

2
1 2

result:

ok 2 lines

Test #5:

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

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: 4ms
memory: 3396kb

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: 39ms
memory: 8956kb

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: 58ms
memory: 10632kb

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: 62ms
memory: 10588kb

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: 68ms
memory: 10632kb

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: 95ms
memory: 10572kb

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: 34ms
memory: 8936kb

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: 35ms
memory: 9012kb

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: 0ms
memory: 3392kb

input:

2
-1000000000 1000000000
1000000000 1000000000

output:

2
1 2

result:

ok 2 lines

Test #15:

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

input:

2
-1000000000 999999999
1000000000 1000000000

output:

2
1 2

result:

ok 2 lines

Test #16:

score: -100
Time Limit Exceeded

input:

2
-1000000000 1000000000
1000000000 999999999

output:

0

result: