QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682636#9156. 百万富翁xieyvzhou12315 628ms28340kbC++144.6kb2024-10-27 16:34:392024-10-27 16:34:41

Judging History

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

  • [2024-10-27 16:34:41]
  • 评测
  • 测评结果：15
  • 用时：628ms
  • 内存：28340kb
查看
  • [2024-10-27 16:34:39]
  • 提交

answer

#include<bits/stdc++.h>
#include"richest.h"
std::vector<int>ask(std::vector<int>a,std::vector<int>b);
int t[1000010];
//level6 return 500000 numbers
std::vector<int> level6(){
	std::vector<int>a,b,ans;
	for(int i=0;i<1000000;i+=2){a.push_back(i);b.push_back(i+1);}
	ans=ask(a,b);
	return ans;
}
//level5 return 250000 numbers
std::vector<int> level5(){
	std::vector<int>a1=level6();
	std::vector<int>a,b,ans;
	for(int i=0;i<500000;i+=2){
		a.push_back(a1[i]);
		b.push_back(a1[i+1]);
	}
	ans=ask(a,b);
	return ans;
}
//level4 return 125000 numbers
std::vector<int> level4(){
	std::vector<int>a1=level5();
	std::vector<int>a,b,ans;
	for(int i=0;i<250000;i+=2){
		a.push_back(a1[i]);
		b.push_back(a1[i+1]);
	}
	ans=ask(a,b);
	return ans;
}
//level3 return 62500 numbers
std::vector<int> level3(){
	std::vector<int>a1=level4();
	std::vector<int>a,b,ans;
	for(int i=0;i<125000;i+=2){
		a.push_back(a1[i]);
		b.push_back(a1[i+1]);
	}
	ans=ask(a,b);
	return ans;
}
//level2 return 20833 numbers
std::vector<int> level2(){
	std::vector<int>a1=level3();
	std::vector<int>ans;
	std::vector<int>a,b;
	for(int i=0;i<20832;i++){
		int a1l=i*3;int a1r=a1l+2;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				a.push_back(a1[j]);
				b.push_back(a1[k]);
			}
		}
	}
	for(int j=62496;j<62500;j++){
		for(int k=62496;k<j;k++){
			a.push_back(a1[j]);
			b.push_back(a1[k]);
		}
	}
	std::vector<int>res=ask(a,b);
	int tot=0;
	memset(t,0,sizeof t);
	for(int i=0;i<20832;i++){
		int a1l=i*3;int a1r=a1l+2;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				t[res[tot]]++;
				tot++;
			}
		}
		for(int j=a1l;j<=a1r;j++){
			if(t[a1[j]]==2)	ans.push_back(a1[j]);
		}
	}
	for(int j=62496;j<62500;j++){
		for(int k=62496;k<j;k++){
			t[res[tot]]++;
			tot++;
		}
	}
	for(int j=62496;j<62500;j++){
		if(t[a1[j]]==3)	ans.push_back(a1[j]);
	}
	return ans;
}
//level1 return 3472 numbers
std::vector<int> level1(){
	std::vector<int>a1=level2();
	std::vector<int>ans;
	std::vector<int>a,b;
	for(int i=0;i<3471;i++){
		int a1l=i*6;int a1r=a1l+5;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				a.push_back(a1[j]);
				b.push_back(a1[k]);
			}
		}
	}
	for(int j=20826;j<20833;j++){
		for(int k=20826;k<j;k++){
			a.push_back(a1[j]);
			b.push_back(a1[k]);
		}
	}
	std::vector<int>res=ask(a,b);
	int tot=0;
	memset(t,0,sizeof t);
	for(int i=0;i<3471;i++){
		int a1l=i*6;int a1r=a1l+5;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				t[res[tot]]++;
				tot++;
			}
		}
		for(int j=a1l;j<=a1r;j++){
			if(t[a1[j]]==5)	ans.push_back(a1[j]);
		}
	}
	for(int j=20826;j<20833;j++){
		for(int k=20826;k<j;k++){
			t[res[tot]]++;
			tot++;
		}
	}
	for(int j=20826;j<20833;j++){
		if(t[a1[j]]==6)	ans.push_back(a1[j]);
	}
	return ans;
}
//level0 return 183 numbers
std::vector<int> level0(){
	std::vector<int>a1=level1();
	std::vector<int>ans;
	std::vector<int>a,b;
	for(int i=0;i<178;i++){
		int a1l=i*19;int a1r=a1l+18;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				a.push_back(a1[j]);
				b.push_back(a1[k]);
			}
		}
	}
	for(int i=0;i<5;i++){
		int a1l=i*19+3382;int a1r=a1l+17;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				a.push_back(a1[j]);
				b.push_back(a1[k]);
			}
		}
	}
	std::vector<int>res=ask(a,b);
	int tot=0;
	memset(t,0,sizeof t);
	for(int i=0;i<178;i++){
		int a1l=i*19;int a1r=a1l+18;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				t[res[tot]]++;
				tot++;
			}
		}
		for(int j=a1l;j<=a1r;j++){
			if(t[a1[j]]==18)	ans.push_back(a1[j]);
		}
	}
	for(int i=0;i<5;i++){
		int a1l=i*19+3382;int a1r=a1l+17;
		for(int j=a1l;j<=a1r;j++){
			for(int k=a1l;k<j;k++){
				t[res[tot]]++;
				tot++;
			}
		}
	}
	for(int i=0;i<5;i++){
		int a1l=i*19+3382;int a1r=a1l+17;
		for(int j=a1l;j<=a1r;j++){
			if(t[a1[j]]==17)	ans.push_back(a1[j]);
		}
	}
	return ans;
}
int richest(int N,int S,int T){
	memset(t,0,sizeof t);
	if(N==1000){
		std::vector<int>a,b;
		int w=0;
		for(int i=0;i<1000;i++){
			for(int j=0;j<i;j++){
				a.push_back(i);
				b.push_back(j);
				w++;
			}
		}
		std::vector<int>c=ask(a,b);
		for(int i=0;i<w;i++){
			t[c[i]]++;
		}
		for(int i=0;i<1000;i++){
			if(t[i]==999)	return i;
		}
	}
	else{
		std::vector<int>a1;
		a1=level0();
		std::vector<int>a,b;
		int w=0;
		for(int i=0;i<183;i++){
			for(int j=0;j<i;j++){
				a.push_back(a1[i]);
				b.push_back(a1[j]);
				w++;
			}
		}
		std::vector<int>c=ask(a,b);
		memset(t,0,sizeof t);
		for(int i=0;i<w;i++){
			t[c[i]]++;
		}
		for(int i=0;i<183;i++){
			if(t[a1[i]]==182)	return a1[i];
		}
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 15
Accepted
time: 614ms
memory: 28340kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 0
Runtime Error

input:

1000000 20 2000000 29091473

output:

Unauthorized output

result:

Final Tests

Test #1:

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

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 0
Runtime Error

input:

1000000 20 2000000 29091471

output:

Unauthorized output

result:
English 繁體中文 简体中文

Server Time: 2025-01-07 23:59:33 | OpenSource Project