QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #492468 | #9156. 百万富翁 | tuxuanming2024# | 68.99999 | 3327ms | 88100kb | C++14 | 1.2kb | 2024-07-26 12:36:57 | 2024-07-26 12:36:57 |
Judging History
answer
#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mx[1005][1005];
ll get(int x,int y) {return x*1000001ll+y;}
void work(vector<int>&p,int B,int t)
{
while((t--)&&(int)p.size()>1)
{
int sz=p.size();
vector<int>a,b;
unordered_map<ll,int>mx;
for(int i=0;i<sz;i+=B)
{
for(int j=i;j<min(sz,i+B);j++)
for(int k=j+1;k<min(sz,i+B);k++) a.push_back(p[j]),b.push_back(p[k]);
}
vector<int>c=ask(a,b),q;
for(int i=0;i<(int)a.size();i++) mx[get(a[i],b[i])]=c[i];
for(int i=0;i<sz;i+=B)
{
int res=p[i];
for(int j=i+1;j<min(sz,i+B);j++)
if(mx[get(res,p[j])]==p[j]) res=p[j];
q.push_back(res);
}
p=q;
}
}
int richest(int n, int T, int S)
{
if(T==1)
{
vector<int>a,b;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++) a.push_back(i),b.push_back(j);
vector<int>c=ask(a,b);
for(int i=0,k=0;i<n;i++)
for(int j=i+1;j<n;j++) mx[i][j]=c[k++];
int ans=0;
for(int i=1;i<n;i++) if(mx[ans][i]==i) ans=i;
return ans;
}
vector<int>p;
for(int i=0;i<n;i++) p.push_back(i);
work(p,2,4);
work(p,5,5);
work(p,20,1);
return p[0];
}
/*
g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static && ./richest
*/
详细
Pretests
Pretest #1:
score: 15
Accepted
time: 629ms
memory: 30928kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 54
Acceptable Answer
time: 3319ms
memory: 88100kb
input:
1000000 20 2000000 29091473
output:
Partially correct Case 2, 54 / 85, maxt = 10, maxs = 1093890 18090236368016981169 0.635294 4439523384460221017
result:
points 0.635294 Partially correct Case 2, 54 / 85, maxt = 10, maxs = 1093890
Final Tests
Test #1:
score: 15
Accepted
time: 619ms
memory: 29940kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 54
Acceptable Answer
time: 3327ms
memory: 87376kb
input:
1000000 20 2000000 29091471
output:
Partially correct Case 2, 54 / 85, maxt = 10, maxs = 1093890 18090236368016981169 0.635294 4439523384460221017
result:
points 0.635294 Partially correct Case 2, 54 / 85, maxt = 10, maxs = 1093890