QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490144#9156. 百万富翁strcmp#0 2ms10248kbC++141.7kb2024-07-25 11:56:022024-07-25 11:56:03

Judging History

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

  • [2024-07-25 11:56:03]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:10248kb
  • [2024-07-25 11:56:02]
  • 提交

answer

#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
#include "richest.h"
#define rep(i, a, b) for(int i = a; i <= b; i++)
using vec = vector<int>;
using ll = long long int;
constexpr int maxn = 2e6 + 10;
#define ps push_back
vec p, np, a, b; int n, t, s, cnt[maxn];
int qry(int l, int r) {
	if (l == r) return p[l];
	a.clear(); b.clear();
	for (int i = l; i < r; i++) {
		for (int j = i + 1; j <= r; j++) a.ps(p[i]), b.ps(p[j]); 
	}
	vec c = ask(a, b); int ans = 0;
	for (int i = 0; i < c.size(); i++) {
		++cnt[c[i]];
		if (cnt[c[i]] == r - l) ans = c[i];
	}
	for (int i = 0; i < c.size(); i++) --cnt[c[i]];
	a.clear(); b.clear();
	return ans;
}
void qwq(int l, int r) {
	for (int i = l; i < r; i++) {
		for (int j = i + 1; j <= r; j++) a.ps(p[i]), b.ps(p[j]); 
	}
}
void divide(int k) {
	if (n < k) return; 
	for (int i = 0; i < n; i += k) {
		int j = min(i + k - 1, n - 1);
		qwq(i, j);
	}
	vec c = ask(a, b); int L = 0;
	for (int i = 0; i < n; i += k) {
		int j = min(i + k - 1, n - 1);
		int len = j - i + 1;
		if (len == 1) { np.ps(p[i]); continue; }
		int wx = len * (len - 1) / 2;
		int R = L + wx - 1, ans = p[i];
		cerr << L << " " << R << "\n";
		for (int k = L; k <= R; k++) {
			++cnt[c[k]];
			if (cnt[c[k]] == len - 1) ans = c[k];
		}
		for (int k = L; k <= R; k++) --cnt[c[k]];
		np.ps(ans); L = R + 1;
	}
	p = np; n = p.size(); np.clear(); a.clear(); b.clear(); 
}
int richest(int N, int T, int S) {
	n = N, t = T, s = S; p.clear(); np.clear();
	for (int i = 0; i < n; i++) p.ps(i);
	//divide(3);
	for (int i = 1; i < t - 4; i++) divide(2);
	divide(3); divide(3); divide(3); divide(3);
	return qry(0, n - 1);
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 0
Wrong Answer
time: 2ms
memory: 10248kb

input:

1000 1 499500 957319859

output:

Too many queries
1294109832092195181
0.000000
6906350380861515327

result:

points 0.0 Too many queries

Pretest #2:

score: 0
Time Limit Exceeded

input:

1000000 20 2000000 29091473

output:

Unauthorized output

result:



Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 10156kb

input:

1000 1 499500 957319857

output:

Too many queries
1294109832092195181
0.000000
6906350380861515327

result:

points 0.0 Too many queries

Test #2:

score: 0
Time Limit Exceeded

input:

1000000 20 2000000 29091471

output:

Unauthorized output

result: