QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527157#9156. 百万富翁TheRaptor81.999975 1922ms89640kbC++171.2kb2024-08-22 11:05:542024-08-22 11:05:54

Judging History

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

  • [2024-08-22 11:05:54]
  • 评测
  • 测评结果:81.999975
  • 用时:1922ms
  • 内存:89640kb
  • [2024-08-22 11:05:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#include "richest.h"
int richest(int n, int t, int s){
	vector<int> a,b,ret;
	if(t==1){
		assert(n==1000);
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				a.push_back(i);
				b.push_back(j);
			}
		}
		ret=ask(a,b);
		int ans=0;
		for(int i=0; i<(int)ret.size(); i++){
			if(a[i]==ans) ans=ret[i];
		}
		return ans;
	}
	vector<int> alive,tmp;
	for(int i=0; i<n; i++) alive.push_back(i);
	int bucs[]={2,2, 2, 2, 3, 6, 19, 183},at=0;
	while((int)alive.size()>1){
		int m=alive.size();
		int buc=bucs[at];
		at++;
		//cout << m << ' ' << buc << '\n';
		//cout << buc << '\n';
		//cout << (m+buc-1)/buc*buc*(buc-1)/2 << '\n';
		a.clear(); b.clear();
		for(int i=0; i<m; i+=buc){
			for(int j=0; j<buc; j++){
				for(int k=j+1; k<buc; k++){
					if(i+j>=m||i+k>=m) continue;
					a.push_back(alive[i+j]);
					b.push_back(alive[i+k]);
				}
			}
		}
		ret=ask(a,b);
		int cnt=0;
		for(int i=0; i<m; i+=buc){
			int best=alive[i];
			for(int j=0; j<buc; j++){
				for(int k=j+1; k<buc; k++){
					if(i+j>=m||i+k>=m) continue;
					if(a[cnt]==best) best=ret[cnt];
					cnt++;
				}
			}
			tmp.push_back(best);
		}
		swap(tmp,alive);
		tmp.clear();
	}
	return alive[0];
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 15
Accepted
time: 596ms
memory: 25284kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 67
Acceptable Answer
time: 1904ms
memory: 89408kb

input:

1000000 20 2000000 29091473

output:

Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960
2586970244946203279
0.788235
12006835993993373281

result:

points 0.788235 Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960


Final Tests

Test #1:

score: 15
Accepted
time: 590ms
memory: 25272kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 67
Acceptable Answer
time: 1922ms
memory: 89640kb

input:

1000000 20 2000000 29091471

output:

Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960
2586970244946203279
0.788235
12006835993993373281

result:

points 0.788235 Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960