QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87265#2365. Flight CollisiontovarischWA 2ms3524kbC++2.3kb2023-03-12 07:32:022023-03-12 07:32:03

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

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.
 *
 * */
const int maxn = 1e5 + 10;
const long long oo = 1e9;
int n; 
int a[maxn], v[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;
	}
};
item t[maxn];
priority_queue <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};
}
bool best(item x, item y) {
	return (double(x.da) / double(x.dv) < double(y.da) / double(y.dv));
}
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);
		t[i] = {oo, 1, i, i};
	}

	for (int i = 0; i + 1 < n; i++) {
		if (check(i, i + 1)) {
			item f = find(i, i + 1);
			if (best(f, t[i])) { 
				t[i] = t[i + 1] = f;
				q.push(f);
			}
		}
	}

	while (!q.empty()) {
		assert(q.size() < n);
		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 && check(l, r)){
				item f = find(l, r);
				if (best(f, t[l]) && best(f, t[r])) {
					q.push(f);
				}
			}
			t[i] = t[j] = find(i, j);
		} else if (in.count(i)) t[i] = {oo, 1, i, i}; 
		else if (in.count(j)) t[j] = {oo, 1, j, j};
	}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

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

input:

5
1 1000000000
2 1000000000
3 -1000000000
4 -1000000000
5 -1000000000

output:

1
5

result:

ok 2 lines

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3356kb

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

3
1 2 3

result:

wrong answer 1st lines differ - expected: '1', found: '3'