QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87250#2365. Flight CollisiontovarischWA 73ms11728kbC++2.3kb2023-03-12 06:38:072023-03-12 06:38:10

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:38:10]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:11728kb
  • [2023-03-12 06:38:07]
  • 提交

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 <double, pii>;
const int maxn = 1e5 + 10;
int n; 
int a[maxn], v[maxn];
set <int> in;
set <pii> comp;
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];
}
double find(int i, int j) {
	if (i > j) swap(i, j);
	return double(a[i] - a[j]) / double(v[j] - v[i]);
}
void match(int i) {
	auto it = in.upper_bound(i);
	if (it != in.end()) {
		int j = *it;
		if (check(i, j)) {
			if (!comp.count({i, j})) {
				q.push({find(i, j), {i, j}});
				comp.insert({i, j});
			}
		}
	}
	it = in.lower_bound(i);
	if (it != in.begin()) {
		it--;
		int j = *it;
		if (check(j, i)) {
			if (!comp.count({i, j})) {
				q.push({find(j, i), {j, i}});
				comp.insert({i, j});
			}
		}
	}
}
void add(int i) {
	auto it = in.upper_bound(i);
	if (it != in.end()) match(*it);
	it = in.lower_bound(i);
	if (it != in.begin()) {
		it--;
		match(*it);
	}
}
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}});
			comp.insert({i, i + 1});
		}
	}

	while (!q.empty()) {
		pdi u = q.top(); q.pop();
		int i = u.second.first, j = u.second.second;
		comp.erase({i, j});
		if (in.count(i) && in.count(j)) {
			in.erase(i);
			in.erase(j);
			add(i);
			add(j);
		} else if (in.count(i)) {
			match(i);
			add(j);
		} else if (in.count(j)){
			match(j);
			add(i);
		} else {
			add(i);
			add(j);
		}
	}
	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: 0ms
memory: 3364kb

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

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

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3

result:

ok 2 lines

Test #4:

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

input:

2
5 4
10 5

output:

2
1 2

result:

ok 2 lines

Test #5:

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

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: 1ms
memory: 3404kb

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

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: 73ms
memory: 11640kb

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: 51ms
memory: 11728kb

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'