QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499321 | #9156. 百万富翁 | cjwen | 91.00003 | 3292ms | 141860kb | C++14 | 2.0kb | 2024-07-31 12:24:18 | 2024-07-31 12:24:18 |
Judging History
answer
#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
int zans;
int llw(vector<int> tp){
int n = tp.size();
vector<int> a, b;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
a.push_back(i);
b.push_back(j);
}
}
vector<int> c = ask(a, b);
vector<bool> d(n, 1);
int ccnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
d[i^j^c[ccnt++]] = 0;
}
}
for(int i = 0; i < n; i++){
if(d[i]){
return i;
}
}
}
int cl[9] = {0, 500000, 250000, 125000, 62500, 20833, 3472, 182, 1};
void doit(int o, vector<int> &tp){
// if(o == 8){
// zans = llw(tp);
// return ;
// }
int n = tp.size();
// printf("doit(%d, %d)\n", o, n);
vector<vector<int> > fz(cl[o]);
for(int i = 0; i < n; i++){
fz[i%cl[o]].push_back(tp[i]);
}
vector<int> nxt;
vector<int> a, b;
for(int k = 0; k < cl[o]; k++){
int m = fz[k].size();
for(int i = 0; i < m; i++){
for(int j = 0; j < i; j++){
a.push_back(fz[k][i]);
b.push_back(fz[k][j]);
}
}
}
vector<int> c = ask(a, b);
int ccnt = 0;
vector<bool> d(1000000, 1);
for(int k = 0; k < cl[o]; k++){
int m = fz[k].size();
for(int i = 0; i < m; i++){
for(int j = 0; j < i; j++){
// printf("%d %d %d\n", fz[k][i], fz[k][j], c[ccnt++]);
d[fz[k][i]^fz[k][j]^c[ccnt++]] = 0;
}
}
}
for(int i = 0; i < n; i++){
if(d[tp[i]]){
nxt.push_back(tp[i]);
}
}
if(o == 8){
zans = nxt[0];
}else{
doit(o+1, nxt);
}
}
int richest(int N, int T, int S) {
vector<int> tp;
for(int i = 0; i < N; i++){
tp.push_back(i);
}
if(N == 1000){
return llw(tp);
}
doit(1, tp);
return zans;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 601ms
memory: 24196kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 76
Acceptable Answer
time: 3180ms
memory: 141860kb
input:
1000000 20 2000000 29091473
output:
Partially correct Case 2, 76 / 85, maxt = 8, maxs = 1099947 708834003727782761 0.894118 11625001216319896173
result:
points 0.894118 Partially correct Case 2, 76 / 85, maxt = 8, maxs = 1099947
Final Tests
Test #1:
score: 15
Accepted
time: 614ms
memory: 22848kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 76
Acceptable Answer
time: 3292ms
memory: 141848kb
input:
1000000 20 2000000 29091471
output:
Partially correct Case 2, 76 / 85, maxt = 8, maxs = 1099947 708834003727782761 0.894118 11625001216319896173
result:
points 0.894118 Partially correct Case 2, 76 / 85, maxt = 8, maxs = 1099947