QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#633588#9460. Diversity and Varianceucup-team5052#AC ✓253ms8712kbC++172.3kb2024-10-12 15:47:412024-10-14 17:20:17

Judging History

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

  • [2024-10-14 17:20:17]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:253ms
  • 内存:8712kb
  • [2024-10-14 17:20:06]
  • hack成功,自动添加数据
  • (/hack/993)
  • [2024-10-12 15:47:42]
  • 评测
  • 测评结果:100
  • 用时:263ms
  • 内存:8628kb
  • [2024-10-12 15:47:41]
  • 提交

answer

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

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 100005, V = 10005;
int n, a[N], m;
vector <int> adj[V];
int cnt[V], ans[N], cvs[N];
long long res = 0;
set <int> mdf[2];

inline void Read() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
		adj[a[i]].push_back(i);
	}
}

inline void Solve() {
	if (m == n - 1) {
		cout << 1 << "\n";
		return;
	}
	sort(a + 1, a + n + 1);
	long long s1 = 0, s2 = 0;
	for (int i = 1;i <= n;i++) ans[i] = cvs[i] = 0;
	for (int i = m + 1;i <= n;i++) {
		ans[adj[a[i]][cnt[a[i]]]] = cvs[adj[a[i]][cnt[a[i]]]] = 1;
		cnt[a[i]]++;
		s1 += a[i];
		s2 += 1ll * a[i] * a[i];
	}
	res = (n - m) * s2 - s1 * s1;
	mdf[0].clear();
	mdf[1].clear();
	for (int i = 1;i <= n - m;i++) {
		cnt[a[i + m]]--;
		int pos = adj[a[i + m]][cnt[a[i + m]]];
		s1 -= a[i + m]; s2 -= 1ll * a[i + m] * a[i + m];
		// cout << pos << " " << cvs[pos] << "\n";
		if (cvs[pos] != ans[pos]) mdf[ans[pos]].erase(pos);
		cvs[pos] = 0;
		if (cvs[pos] != ans[pos]) mdf[ans[pos]].insert(pos);
		
		pos = adj[a[i]][cnt[a[i]]];
		cnt[a[i]]++;
		s1 += a[i]; s2 += 1ll * a[i] * a[i];
		// cout << pos << " " << cvs[pos] << "\n";
		if (cvs[pos] != ans[pos]) mdf[ans[pos]].erase(pos);
		cvs[pos] = 1;
		if (cvs[pos] != ans[pos]) mdf[ans[pos]].insert(pos);
		if ((n - m) * s2 - s1 * s1 > res || ((n - m) * s2 - s1 * s1 == res && !mdf[0].empty() && *(mdf[0].begin()) < *(mdf[1].begin()))) {
			for (int x : mdf[0]) ans[x] = cvs[x];
			for (int x : mdf[1]) ans[x] = cvs[x];
			// cout << (n - m) * s2 - s1 * s1 << endl;
			// for (int i = 1;i <= n;i++) cout << cvs[i] << ' ';
			// cout << endl;
			mdf[0].clear();
			mdf[1].clear();
			res = (n - m) * s2 - s1 * s1;
		}
	}
	int cnt1 = 0;
	for (int i = 1;i <= n;i++) {
		if (ans[i]) {
			cnt1++;
			cout << i << " \n"[cnt1 == n - m];
		}
	}
}

inline void Clear() {
/*
	int n, a[N];
vector <int> adj[V];
int cnt[V], ans[N], cvs[N];
long long res = 0;
set <int> mdf[2];*/
	for (int i = 1;i <= n;i++) {
		adj[a[i]].clear();
		cnt[a[i]] = 0;
		ans[i] = cvs[i] = 0;
	}
	res = 0;
	mdf[0].clear();
	mdf[1].clear();
}

int main() {
	std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		Read();
		Solve();
		Clear();
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9
3 2
34 35 36
4 2
20 35 41 74
5 2
40 30 50 20 10
5 2
50 40 30 20 10
5 2
10 20 30 40 50
5 3
30 40 20 10 50
5 4
10 20 30 40 50
5 1
30 50 40 20 10
5 0
30 50 40 20 10

output:

1
1 4
1 3 5
1 2 5
1 2 5
4 5
1
2 3 4 5
1 2 3 4 5

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 253ms
memory: 8712kb

input:

30713
38 30
2 3 8 2 0 0 4 4 5 4 8 1 2 1 3 2 0 9 5 6 6 4 8 8 1 4 6 2 3 2 0 9 2 5 8 2 3 2
8 1
5222 2247 8017 1046 1922 9545 1396 2722
8 4
99 99 99 9999 999 9 1 9999
99 98
1 3 3 3 8 8 9 7 3 8 0 6 5 6 1 5 3 7 8 6 4 5 4 5 7 9 6 7 0 5 0 0 9 0 9 0 1 1 3 1 4 5 9 2 8 8 1 2 8 0 1 2 3 6 3 9 1 6 2 7 8 0 5 3 8 7...

output:

3 5 6 11 17 18 31 32
2 3 4 5 6 7 8
4 6 7 8
1
1 2 4 5 7 8
1 5
1 2 3
1 2 3 4 6 7 8
1
11 14 19 22 28 31 35 37 38 39 45 46 47 51 54 59 64 68 74 77 82 85 86 91 95
1
1 3
1 3 4 5 6 7 8 10 13 14 17 19 23 24 25 26 27 33 39 40
1
1 2 3 4 5 6 7
1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 19 20 21 23 24 25 26 27 28 ...

result:

ok 30713 lines

Extra Test:

score: 0
Extra Test Passed