QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#492644#9156. 百万富翁leihonglongyin15 744ms87892kbC++141.4kb2024-07-26 14:52:582024-07-26 14:52:58

Judging History

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

  • [2024-07-26 14:52:58]
  • 评测
  • 测评结果:15
  • 用时:744ms
  • 内存:87892kb
  • [2024-07-26 14:52:58]
  • 提交

answer

#include "richest.h"
#include<bits/stdc++.h>
using namespace std;mt19937 R(time(0));
vector<int>now,a,b,tmp,to;map<int,int>cnt;int tot,Tot;
void sol0(){cnt.clear(),a.clear(),b.clear();int len=now.size();
	for(int i=0;i<len;i++)for(int j=i+1;j<len;j++)
		a.push_back(now[i]),b.push_back(now[j]);
	tmp=ask(a,b),now.resize(1);for(auto i:tmp)cnt[i]++;
	for(auto i:cnt)if(i.second==len-1)return now[0]=i.first,void();
}
void sol1(int len,int x){
	while(tot<x){a.clear(),b.clear(),tmp.clear(),to.clear();
    	shuffle(now.begin(),now.end(),R),tot++;vector<int>id;
		for(int i=0;i<now.size()/len;i++)id.push_back(len);
		int sy=now.size()%len;
		if(sy){id.push_back(len);for(int i=1;i<=sy;i++)id[id.size()-i]--;}
    	for(int l=0,r,i=0;i<id.size();l=r+1,i++){r=l+id[i]-1; 
			for(int x=l;x<=r;x++)for(int y=x+1;y<=r;y++)
				a.push_back(now[x]),b.push_back(now[y]);
		}Tot+=a.size(),tmp=ask(a,b);int num=0;
		for(int l=0,r,i=0;i<id.size();l=r+1,i++){cnt.clear(),r=l+id[i]-1; 
			for(int x=l;x<=r;x++)for(int y=x+1;y<=r;y++)
				cnt[tmp[num++]]++;
			for(int j=l;j<=r;j++)if(cnt[now[j]]==r-l)to.push_back(now[j]);
		}now=to;
	}
}
int richest(int N,int T,int S){now.clear(),Tot=tot=0;
	if(T==1){for(int i=0;i<N;i++)now.push_back(i);return sol0(),now[0];}
	for(int i=0;i<N;i++)now.push_back(i);
	sol1(2,4),sol1(3,5),sol1(6,6),sol1(19,7);
	return sol0(),now[0];
}

詳細信息


Pretests

Pretest #1:

score: 15
Accepted
time: 742ms
memory: 24292kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 0
Wrong Answer
time: 354ms
memory: 87700kb

input:

1000000 20 2000000 29091473

output:

Wrong answer
4459638610240858557
0.000000
6906350380861515327

result:

points 0.0 Wrong answer


Final Tests

Test #1:

score: 15
Accepted
time: 744ms
memory: 22480kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 0
Wrong Answer
time: 353ms
memory: 87892kb

input:

1000000 20 2000000 29091471

output:

Wrong answer
4459638610240858557
0.000000
6906350380861515327

result:

points 0.0 Wrong answer