QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #492261 | #9156. 百万富翁 | leihonglongyin# | 43.00002 | 2993ms | 109812kb | C++14 | 1.1kb | 2024-07-26 10:55:08 | 2024-07-26 10:55:10 |
Judging History
answer
#include "richest.h"
#include<bits/stdc++.h>
using namespace std;int cnt[1005];mt19937 R(time(0));
int richest(int N,int T,int S){vector<int>now,a,b,tmp,to;
if(T==1){memset(cnt,0,sizeof(cnt));
for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)a.push_back(i),b.push_back(j);
now=ask(a,b);for(auto i:now)cnt[i]++;
for(int i=0;i<N;i++)if(cnt[i]==N-1)return i;
}
int tot=0;
for(int i=0;i<N;i++)now.push_back(i);
while(now.size()>200000){a.clear(),b.clear(),tot++;int lst=0;
for(int i=0;i+1<now.size();i+=2)a.push_back(now[i]),b.push_back(now[i+1]);
if(now.size()&1)lst=now.back();
now=ask(a,b);if(lst)now.push_back(lst);
}
cerr<<tot<<"\n";
while(now.size()>1){a.clear(),b.clear(),tmp.clear(),to.clear();
shuffle(now.begin(),now.end(),R);
for(int i=0;i+1<now.size();i++)a.push_back(now[i]),b.push_back(now[i+1]);
tmp=ask(a,b);
if(tmp[0]==now[0])to.push_back(now[0]);
if(tmp.back()==now.back())to.push_back(now.back());
for(int i=0;i+1<tmp.size();i++){
if(tmp[i]==tmp[i+1])to.push_back(now[i+1]);
}now=to;
}
return now[0];
}
/*
1000000 20 2000000 1234
*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 627ms
memory: 25468kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 28
Acceptable Answer
time: 2993ms
memory: 109812kb
input:
1000000 20 2000000 29091473
output:
Partially correct Case 2, 28 / 85, maxt = 15, maxs = 1081371 11515334169781932635 0.329412 5031514366929718649
result:
points 0.329412 Partially correct Case 2, 28 / 85, maxt = 15, maxs = 1081371
Final Tests
Test #1:
score: 15
Accepted
time: 618ms
memory: 25336kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 28
Acceptable Answer
time: 2980ms
memory: 95596kb
input:
1000000 20 2000000 29091471
output:
Partially correct Case 2, 28 / 85, maxt = 15, maxs = 1081175 4580680507098234879 0.329412 5031514366929718649
result:
points 0.329412 Partially correct Case 2, 28 / 85, maxt = 15, maxs = 1081175