QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415569#862. Social JusticeAtalasion#WA 3ms7924kbC++141.9kb2024-05-21 00:16:172024-05-21 00:16:19

Judging History

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

  • [2024-05-21 00:16:19]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7924kb
  • [2024-05-21 00:16:17]
  • 提交

answer


#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;
const int H = 313;

int n, p, q, can[N];
ll ps[N];
pii a[N];

bool isval(int x){
	for (int i = x; i <= n; i++){
		ll sum = ps[i] - ps[i - x];
		if (a[i].F * 1ll * x * 1ll * q <= sum * p) return 1;
	}
	return 0;
}

void Main(){
	cin >> n;
	map<int, int> isc;
	for (int i = 1; i <= n; i++){
		int x;
		cin >> x;
		a[i] = {x, i};
		ps[i] = 0;
		can[i] = 0;
	}
	sort(a + 1, a + n + 1);
	int l = 1, r = n + 1;
	cin >> p >> q;
	for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i].F;
	while (r - l > 1){
		int md = (l + r) >> 1;
		if (isval(md)) l = md;
		else r = md;
	}
//	cout << "AFA " << l << endl; 
	for (int i = l; i <= n; i++){
		ll sum = ps[i] - ps[i - l];
		if (a[i].F * 1ll * l * 1ll * q <= sum * p) {can[i] = 1;}
		else can[i] = 0;
	}
	for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + can[i];
	vi ans;
	vi tmp;
	for (int i = 1; i <= n; i++){
		if (ps[min(i + l - 1, n)] - ps[i - 1] == 0) tmp.pb(i);
		else isc[a[i].F] = 1;
	}
	int mn = INF;
	for (int i = n - l; i >= 1; i--){
		mn = min(mn, l * a[i + l].F * q - (ps[i + l] - ps[i]) * p);
		if (mn <= a[i].F * p) isc[a[i].F] = 1; 
	}
	for (int i = 1; i <= n; i++){
		if (isc[a[i].F] == 0) ans.pb(a[i].S);
	}
	cout << ans.size() << '\n';
	sort(all(ans));
	for (auto u:ans) cout << u << ' ';
	cout << '\n';
	return;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) Main();
	



}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5840kb

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: 3ms
memory: 7924kb

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 735th numbers differ - expected: '0', found: '9'