QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87255#2365. Flight CollisiontovarischWA 2ms3524kbC++2.0kb2023-03-12 06:55:402023-03-12 06:55:42

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:55:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3524kb
  • [2023-03-12 06:55:40]
  • 提交

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 <pii, pii>;
const int maxn = 1e5 + 10;
int n; 
int a[maxn], v[maxn];
bool wt[maxn];
set <int> in;
struct item {
	long long da, dv;
	int i, j;
	bool operator > (const item& b) const {
		return da * b.dv > b.da * dv;
	}
};
priority_queue <item, vector <item>, greater<item>> q;
bool check(int i, int j) {
	if (i > j) swap(i, j);
	return v[i] > v[j];
}
item find(int i, int j) {
	if (i > j) swap(i, j);
	long long da = a[i] - a[j], dv = v[j] - v[i];
	return {da, dv, i, j};
}
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));
			wt[i] = wt[i + 1] = 1;
		}
	}

	while (!q.empty()) {
		item u = q.top(); q.pop();
		int i = u.i, j = u.j;
		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 && !wt[l] && !wt[r] && check(l, r)){
				q.push(find(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: 3332kb

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

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

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

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3

result:

ok 2 lines

Test #4:

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

input:

2
5 4
10 5

output:

2
1 2

result:

ok 2 lines

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3524kb

input:

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

output:

1
9

result:

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