QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #492389 | #9156. 百万富翁 | Dawnq# | 15 | 625ms | 62392kb | C++14 | 2.9kb | 2024-07-26 11:50:45 | 2024-07-26 11:50:46 |
Judging History
answer
#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1e6+5;
int richest(int n,int s,int t){
vector<int>a,b,c;
if(n==1000){
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j)a.push_back(i),b.push_back(j);
}
c=ask(a,b);
vector<int>rd(n,0);
for(int i=0;i<499500;++i){
if(c[i]==a[i])++rd[b[i]];
else ++rd[a[i]];
}
for(int i=0;i<n;++i)if(!rd[i])return i;
}
vector<int>p(n);
for(int i=0;i<n;++i)p[i]=i;
a.clear(),b.clear();for(int i=0;i<1000000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
p=ask(a,b);
a.clear(),b.clear();for(int i=0;i<500000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
p=ask(a,b);
a.clear(),b.clear();for(int i=0;i<250000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
p=ask(a,b);
a.clear(),b.clear();for(int i=0;i<125000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
p=ask(a,b);
{
a.clear(),b.clear();
int k0=p[62499];
for(int i=0;i<62499;i+=3){
a.push_back(p[i]),a.push_back(p[i+1]);
a.push_back(p[i+1]),a.push_back(p[i+2]);
a.push_back(p[i+2]),a.push_back(p[i]);
}
c=ask(a,b);
vector<int>rd(n,0),q;
for(int i=0;i<62499;++i)++rd[c[i]];
for(int i=0;i<62499;++i)if(rd[p[i]]==2)q.push_back(p[i]);
p=q,p.push_back(k0);
}
{
a.clear(),b.clear();
int k0=p[20833],k1=p[20832];
for(int i=0;i<20832;i+=6){
for(int j=0;j<6;++j){
for(int k=j+1;k<6;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
}
}
a.push_back(k0),b.push_back(k1);
c=ask(a,b);
vector<int>rd(n,0),q;
for(int i=0;i<52080;++i)++rd[c[i]];
for(int i=0;i<20832;++i)if(rd[p[i]]==5)q.push_back(p[i]);
p=q,p.push_back(c[52080]);
}
{
a.clear(),b.clear();
for(int i=0;i<3173;i+=19){
for(int j=0;j<19;++j){
for(int k=j+1;k<19;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
}
}
for(int i=3173;i<3473;i+=20){
for(int j=0;j<20;++j){
for(int k=j+1;k<20;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
}
}
c=ask(a,b);
vector<int>rd(n,0),q;
for(int i=0;i<(int)c.size();++i)++rd[c[i]];
for(int i=0;i<3173;++i)if(rd[p[i]]==18)q.push_back(p[i]);
for(int i=3173;i<3473;++i)if(rd[p[i]]==19)q.push_back(p[i]);
p=q;
}
{
a.clear(),b.clear();
for(int j=0;j<182;++j){
for(int k=j+1;k<182;++k)a.push_back(p[j]),b.push_back(p[k]);
}
c=ask(a,b);
vector<int>rd(n,0),q;
for(int i=0;i<(int)c.size();++i)++rd[c[i]];
for(int i=0;i<182;++i)if(rd[p[i]]==181)q.push_back(p[i]);
return q[0];
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 610ms
memory: 25268kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 0
Wrong Answer
time: 64ms
memory: 62372kb
input:
1000000 20 2000000 29091473
output:
Protocol violation: i and j have different sizes 1404982681567508643 0.000000 6906350380861515327
result:
points 0.0 Protocol violation: i and j have different sizes
Final Tests
Test #1:
score: 15
Accepted
time: 625ms
memory: 25296kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 0
Wrong Answer
time: 76ms
memory: 62392kb
input:
1000000 20 2000000 29091471
output:
Protocol violation: i and j have different sizes 1404982681567508643 0.000000 6906350380861515327
result:
points 0.0 Protocol violation: i and j have different sizes