QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#502302#9156. 百万富翁Insert_Username_Here#15 1988ms98136kbC++201.7kb2024-08-03 03:21:442024-08-03 03:21:47

Judging History

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

  • [2024-08-03 03:21:47]
  • 评测
  • 测评结果:15
  • 用时:1988ms
  • 内存:98136kb
  • [2024-08-03 03:21:44]
  • 提交

answer

#include "richest.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 1e9 + 7;
// cope counter = 2254

int num[8] = {1, 2, 2, 2, 2, 3, 6, 19};
vector<int> arr, nxt, a, b, c, diff;

int richest(int st, int end) {
	int rich = 0, i = st;
	for(; i < min((int)a.size(), end); i++) {
		if(i == st || a[i] != a[i - 1]) {
			if(rich) return a[i - 1];
			rich = 1;
		}
		if(c[i] != a[i]) rich = 0;
	}
	return c[i - 1];
}
int bf() {
	int n = arr.size();
	if(n == 1) return arr[0];
	a.clear(), b.clear();
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) a.push_back(arr[i]), b.push_back(arr[j]);
	}
	c = ask(a, b);
	return richest(0, a.size());
}
int richest(int n, int t, int s) {
	arr.resize(n);
	for(int i = 0; i < n; i++) arr[i] = i;
	if(t == 1) return bf();
	for(int i = 1; i < 8; i++) {
		a.clear(), b.clear(), diff.clear();
		int sum = 0;
		while(sum < n) {
			if(num[i] == 6 && sum < 20) diff.push_back(5);
			else if(num[i] == 19 && sum < 72) diff.push_back(18);
			else diff.push_back(num[i]);
			sum += diff.back();
		}
		for(int j = 0, cur = 0; j < n; j += diff[cur], cur++) {
			for(int i2 = j; i2 < min(n, j + diff[cur]); i2++) {
				for(int j2 = i2 + 1; j2 < min(n, j + diff[cur]); j2++) a.push_back(arr[i2]), b.push_back(arr[j2]);
			}
		}
		c = ask(a, b);
		nxt.clear();
		for(int st = 0, i = 0; st < (int)a.size(); st += diff[i] * (diff[i] - 1) / 2, i++) nxt.push_back(richest(st, st + diff[i] * (diff[i] - 1) / 2));
		while(b.back() != arr.back()) nxt.push_back(arr.back()), arr.pop_back();
		arr = nxt, n = arr.size();
		cout << arr.size() << "\n";
	}
	return bf();
}

詳細信息


Pretests

Pretest #1:

score: 15
Accepted
time: 607ms
memory: 24268kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 0
Wrong Answer
time: 1960ms
memory: 97864kb

input:

1000000 20 2000000 29091473

output:

Unauthorized output

result:

points 0.0 Invalid signature


Final Tests

Test #1:

score: 15
Accepted
time: 606ms
memory: 24128kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 0
Wrong Answer
time: 1988ms
memory: 98136kb

input:

1000000 20 2000000 29091471

output:

Unauthorized output

result:

points 0.0 Invalid signature