QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#874487#862. Social Justiceasdfsdf#WA 2ms7908kbC++231.6kb2025-01-28 08:07:442025-01-28 08:07:45

Judging History

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

  • [2025-01-28 08:07:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7908kb
  • [2025-01-28 08:07:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 303030
#define MOD 1'000'000'007
int A[MAX];
int loc[MAX];
ll S[MAX];
int chk[MAX];
int ans[MAX];
void solve() {
	int N;
	cin >> N;
	ll P, Q;
	int i, a;
	vector<pii> in;
	for (i = 1; i <= N; i++) chk[i] = ans[i] = 0;
	for (i = 1; i <= N; i++) {
		cin >> a;
		in.emplace_back(a, i);
	}
	cin >> P >> Q;
	sort(in.begin(), in.end());
	for (i = 1; i <= N; i++) {
		A[i] = in[i - 1].first;
		loc[i] = in[i - 1].second;
		S[i] = S[i - 1] + A[i];
	}
	int l, r;
	l = 1;
	r = N + 1;
	while (r - l > 1) {
		int m = l + r >> 1;
		int chk = 0;
		for (i = m; i <= N; i++) {
			ll s = S[i] - S[i - m];
			if (s * P >= Q * m * A[i]) {
				chk = 1;
				break;
			}
		}
		if (chk) l = m;
		else r = m;
	}
	ll mx = -1;
	for (i = l; i <= N; i++) {
		ll s = S[i] - S[i - l];
		if (s * P >= Q * l * A[i]) chk[i - l + 1] = 1;
	}
	int lv = -N - 1557;
	for (i = 1; i <= N; i++) {
		if (chk[i]) lv = i;
		if (i - lv < l) ans[i] = 1;
	}
	ll mn = 2e9;
	for (i = N - l; i >= 1; i--) {
		ll a = A[i + l];
		ll s = A[i + l] - A[i + 1];
		ll x = a * l * Q - P * s;
		x = (x + P - 1) / P;
		mn = min(mn, x);
		if (mn <= A[i]) ans[i] = 1;
	}
	vector<int> ansv;
	for (i = 1; i <= N; i++) if (!ans[i]) ansv.push_back(loc[i]);
	sort(ansv.begin(), ansv.end());
	cout << ansv.size() << '\n';
	for (auto v : ansv) cout << v << ' ';
	cout << '\n';
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T--) solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5736kb

input:

3
4
1 2 3 4
3 2
5
1 15 2 5 1
2 1
5
1 2 3 1000 10000
4 3

output:

0

1
2 
2
4 5 

result:

ok 6 numbers

Test #2:

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

input:

1000
1
10
3 2
2
10 100
3 2
3
10 10 100
3 2
4
1 2 3 4
3 2
5
1 15 2 5 1
2 1
5
1 2 3 1000 10000
4 3
6
1 2 3 4 1000 10000
4 3
5
50000 2 1 1 5000
2 1
10
1 15 2 5 1 10000 1 1 1 1
2 1
20
1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1
2 1
25
1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1
2 ...

output:

0

0

1
3 
0

1
2 
2
4 5 
3
1 5 6 
2
1 5 
3
2 4 6 
6
2 4 6 12 14 16 
8
2 4 6 12 14 16 22 24 
13
1 2 3 4 5 6 7 8 9 10 11 12 20 
15
1 2 3 4 5 6 7 8 9 10 11 12 18 19 20 
0

2
2 8 
2
9 12 
2
2 14 
10
1 4 5 6 7 13 14 15 18 20 
2
9 16 
2
16 18 
2
5 13 
10
4 5 6 9 11 15 16 18 19 20 
2
5 19 
2
5 13 
2
10 15...

result:

wrong answer 470th numbers differ - expected: '9', found: '10'