QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50351#862. Social JusticeSGColinWA 4ms3720kbC++171.5kb2022-09-25 15:30:242022-09-25 15:30:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-25 15:30:24]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3720kb
  • [2022-09-25 15:30:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = false;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr     first
#define sc     second
#define pb     push_back
#define mp     make_pair
#define pii    pair<int, int>
#define all(x) (x).begin(), (x).end() 

#define N 200007

int pos[N];

pair<int, int> a[N];

ll p, q, sum[N];

vector<int> res;

inline bool check(int l, int r) {
	return (sum[r] - sum[l]) * p >= (r - l) * q * a[r].fr;
}

inline void work() {
	int n = rd();
	for (int i = 1; i <= n; ++i) {
		a[i].fr = rd(); a[i].sc = i;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i].fr;
	p = rd(), q = rd();
	int r = 1;
	while (r < n && check(0, r + 1)) ++r;
	pos[0] = r;
	int ans = n - r;
	for (int l = 1; l < n; ++l) {
		while (r < n && check(l, r + 1)) ++r;
		pos[l] = r;
		ans = min(ans, n - r + l);
	}
	int L = n, R = 0;
	for (int l = 0; l < n; ++l)
		if (n - pos[l] + l == ans) {
			L = min(L, l);
			R = max(R, pos[l]);
		}
	while (a[L].fr == a[L + 1].fr) --L;
	++R;
	while (a[R].fr == a[R - 1].fr) ++R;
	printf("%d\n", L + n - R + 1);
	res.clear();
	for (int i = 1; i <= L; ++i) res.pb(a[i].sc);
	for (int i = R; i <= n; ++i) res.pb(a[i].sc);
	sort(all(res));
	for (auto x : res) printf("%d ", x);
	puts("");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

0

1
12 
0

10
1 4 5 6 7 13 14 15 18 20 
1
16 
1
18 
1
13 
10
4 5 6 9 11 15 16 18 19 20 
0

0

1
10 
0

10
1 2 4 6 8 9 11 13 18 20...

result:

wrong answer 69th numbers differ - expected: '2', found: '0'