QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488174#9156. 百万富翁lfxxx100 ✓2358ms99584kbC++141.6kb2024-07-23 17:20:162024-07-23 17:20:18

Judging History

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

  • [2024-07-23 17:20:18]
  • 评测
  • 测评结果:100
  • 用时:2358ms
  • 内存:99584kb
  • [2024-07-23 17:20:16]
  • 提交

answer

#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
namespace t1 {
int n = 1000, cnt[1005];
int solve()
{
	memset(cnt, 0, sizeof cnt);
	vector<int>a, b;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			a.emplace_back(i);
			b.emplace_back(j);
		}
	}
	vector<int> c = ask(a, b);
	for (int x : c) ++cnt[x];
	return max_element(cnt + 1, cnt + 1 + n) - cnt;
}
}
vector<int>v, vv, a, b, c;
int t[] = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1}, cnt[1000005], tot = 0;
inline void query(int l, int r)
{
	for (int i = l; i <= r; ++i) {
		for (int j = l; j < i; ++j) {
			a.emplace_back(v[i]);
			b.emplace_back(v[j]);
		}
	}
}
inline int query2(int l, int r)
{
	for (int i = l; i <= r; ++i) cnt[v[i]] = 0;
	for (int i = l; i <= r; ++i) {
		for (int j = l; j < i; ++j) {
			++cnt[c[tot++]];
		}
	}
	int id = l;
	for (int i = l + 1; i <= r; ++i) {
		if (cnt[v[i]] > cnt[v[id]]) {
			id = i;
		}
	}
	return v[id];
}
int richest(int N, int T, int S) {
	if (T == 1) return t1::solve();
	v.resize(N);
	for (int i = 0; i < N; ++i) v[i] = i;
	for (int k = 0; v.size() > 1; ++k) {
		// for (int x : v) cerr << x << ' '; cerr << '\n';
		tot = 0;
		a.clear(), b.clear(), vv.clear();
		int cnt = t[k], L = 0;
		for (int i = 0; i < cnt; ++i) {
			query(L, L + v.size() / cnt + (i < v.size() % cnt) - 1);
			L += v.size() / cnt + (i < v.size() % cnt);
		}
		c = ask(a, b);
		L = 0;
		for (int i = 0; i < cnt; ++i) {
			vv.emplace_back(query2(L, L + v.size() / cnt + (i < v.size() % cnt) - 1));
			L += v.size() / cnt + (i < v.size() % cnt);
		}
		v = vv;
	}
	return v[0];
}

詳細信息


Pretests

Pretest #1:

score: 15
Accepted
time: 621ms
memory: 23012kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 85
Accepted
time: 2336ms
memory: 99584kb

input:

1000000 20 2000000 29091473

output:

Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944
7610580723948932399
1.000000
1331569654267968081

result:

points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944


Final Tests

Test #1:

score: 15
Accepted
time: 628ms
memory: 22884kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 85
Accepted
time: 2358ms
memory: 96728kb

input:

1000000 20 2000000 29091471

output:

Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944
7610580723948932399
1.000000
1331569654267968081

result:

points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944