QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #682796 | #9156. 百万富翁 | xieyvzhou123 | 100 ✓ | 1943ms | 101212kb | C++14 | 4.6kb | 2024-10-27 17:23:18 | 2024-10-27 17:23:21 |
Judging History
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*18+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*18+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*18+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];
}
}
}
详细
Pretests
Pretest #1:
score: 15
Accepted
time: 619ms
memory: 26900kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 85
Accepted
time: 1943ms
memory: 101212kb
input:
1000000 20 2000000 29091473
output:
Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944 7610580723948932399 1.000000 1331569654267968081
result:
points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944
Final Tests
Test #1:
score: 15
Accepted
time: 619ms
memory: 28108kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 85
Accepted
time: 1913ms
memory: 90380kb
input:
1000000 20 2000000 29091471
output:
Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944 7610580723948932399 1.000000 1331569654267968081
result:
points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944