QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#493246 | #9156. 百万富翁 | pengyule | 15 | 631ms | 86336kb | C++14 | 3.2kb | 2024-07-26 22:51:23 | 2024-07-26 22:51:24 |
Judging History
answer
#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int baoli[1005][1005],bin[20][20];
int richest(int n,int T,int S) {
if(n==1000){
vector<int>a,b,ret;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)a.emplace_back(i),b.emplace_back(j);
ret=ask(a,b);
int o=0;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)baoli[i][j]=(ret[o]==i),o++;
int now=0;
for(int i=1;i<n;i++)if(!baoli[now][i])now=i;
return now;
}
vector<int>s;
for(int i=0;i<n;i++)s.emplace_back(i);
int U=4;
while(U--){
vector<int>e;
int mid=((int)s.size()+1>>1);
vector<int>a,b,ret;
for(int i=0;i<mid;i++){
if(i+mid>=s.size())e.emplace_back(s[i]);
else a.emplace_back(s[i]),b.emplace_back(s[i+mid]);
}
ret=ask(a,b);
int o=0;
for(int i=0;i<mid;i++){
if(i+mid>=s.size())continue;
else {
if(ret[o]==s[i])e.emplace_back(s[i]);
else e.emplace_back(s[i+mid]);
o++;
}
}
s=e;
}
{
vector<int>a,b,ret,e;
for(int i=0;i<s.size();i+=3){
if(i+2<s.size()){
a.emplace_back(s[i]),b.emplace_back(s[i+1]);
a.emplace_back(s[i]),b.emplace_back(s[i+2]);
a.emplace_back(s[i+1]),b.emplace_back(s[i+2]);
}
else if(i+1<s.size()){
a.emplace_back(s[i]),b.emplace_back(s[i+1]);
}
else {
e.emplace_back(s[i]);
}
}
ret=ask(a,b);
int o=0;
for(int i=0;i<s.size();i+=3){
if(i+2<s.size()){
if(ret[o]==s[i]&&ret[o+1]==s[i])e.emplace_back(s[i]);
else if(ret[o]==s[i+1]&&ret[o+2]==s[i+1])e.emplace_back(s[i+1]);
else e.emplace_back(s[i+2]);
o+=3;
}
else if(i+1<s.size()){
if(ret[o]==s[i])e.emplace_back(s[i]);
else e.emplace_back(s[i+1]);
o++;
}
}
s=e;
}
{
int blo=6;
vector<int>a,b,ret,e;
for(int i=0;i<s.size();i+=blo){
for(int j=i;j<min((int)s.size(),i+blo);j++)
for(int k=j+1;k<min((int)s.size(),i+blo);k++){
a.emplace_back(s[j]),b.emplace_back(s[k]);
}
}
ret=ask(a,b);
int o=0;
for(int i=0;i<s.size();i+=blo){
int p=i;
for(int j=i;j<min((int)s.size(),i+blo);j++)
for(int k=j+1;k<min((int)s.size(),i+blo);k++){
bin[j-i][k-i]=(ret[o]==s[j]);
o++;
}
for(int j=i+1;j<min((int)s.size(),i+blo);j++){
if(!bin[p-i][j-i])p=j;
}
e.emplace_back(s[p]);
}
s=e;
}
cerr<<s.size()<<"||\n";
int len=19;
int w=(int)(s.size()+len-1)/len;
vector<int>a,b,ret,e;
for(int i=0;i+len<s.size();i+=len){
for(int j=i;j<min((int)s.size()-1,i+len);j++)
for(int k=j+1;k<min((int)s.size()-1,i+len);k++){
a.emplace_back(s[j]),b.emplace_back(s[k]);
}
}
ret=ask(a,b);
int o=0;
for(int i=0;i<s.size();i+=len){
int p=i;
for(int j=i;j<min((int)s.size(),i+len);j++)
for(int k=j+1;k<min((int)s.size(),i+len);k++){
bin[j-i][k-i]=(ret[o]==s[j]);
o++;
}
for(int j=i+1;j<min((int)s.size(),i+len);j++){
if(!bin[p-i][j-i])p=j;
}
e.emplace_back(s[p]);
}
s=e;
a.clear(),b.clear(),ret.clear();
n=s.size();
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)a.emplace_back(s[i]),b.emplace_back(s[j]);
ret=ask(a,b);
o=0;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)baoli[i][j]=(ret[o]==s[i]),o++;
int now=0;
for(int i=1;i<n;i++)if(!baoli[now][i])now=i;
return s[now];
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 615ms
memory: 30864kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 0
Wrong Answer
time: 212ms
memory: 85992kb
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: 631ms
memory: 29324kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 0
Wrong Answer
time: 205ms
memory: 86336kb
input:
1000000 20 2000000 29091471
output:
Wrong answer 4459638610240858557 0.000000 6906350380861515327
result:
points 0.0 Wrong answer