QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487508#9156. 百万富翁TulipeNoire82.568625 2618ms90040kbC++142.3kb2024-07-22 22:47:482024-07-22 22:47:49

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 22:47:49]
  • 评测
  • 测评结果:82.568625
  • 用时:2618ms
  • 内存:90040kb
  • [2024-07-22 22:47:48]
  • 提交

answer

#include<bits/stdc++.h>
#include"richest.h"
#define pb(x) push_back(x)
using namespace std;
using vi=vector<int>;
const int N=1005;
int mat[N][N];
int c[9]={0,2,2,2,2,3,6,19,183};
int richest(int n, int t, int s) {
    memset(mat,0,sizeof mat);
    if (n<=1000) {
        vi a,b;
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                a.pb(i),b.pb(j);
            }
        }
        auto res=ask(a,b);
        int ct=0;
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                int x=res[ct++];
                if (x==i) mat[i][j]=1;
                else mat[j][i]=1;
            }
        }
        for (int i=0;i<n;i++) {
            int coef=1;
            for (int j=0;j<n;j++) {
                if (i==j) continue;
                if (!mat[i][j]) coef=0;
            }
            if (coef) return i;
        }
    }
    vi cand;
    for (int i=0;i<n;i++) cand.pb(i);
    for (int i=1;i<=8;i++) {
        vi a,b,tmp;
        for (int j=0;j<cand.size();j+=c[i]) {
            for (int k=0;k<c[i];k++) {
                for (int u=0;u<c[i];u++) mat[k][u]=0;
            }
            int l=j,r=min(j+c[i]-1,(int)cand.size()-1);
            for (int k=l;k<=r;k++) {
                for (int u=k+1;u<=r;u++) {
                    // if (k==u) continue;
                    a.pb(cand[k]),b.pb(cand[u]);
                }
            }
        }
        auto res=ask(a,b);
        int ct=0;
        for (int j=0;j<cand.size();j+=c[i]) {
            for (int k=0;k<c[i];k++) {
                for (int u=0;u<c[i];u++) mat[k][u]=0;
            }
            int l=j,r=min(j+c[i]-1,(int)cand.size()-1);
            for (int k=l;k<=r;k++) {
                for (int u=k+1;u<=r;u++) {
                    // if (k==u) continue;
                    // a.pb(k),b.pb(u);
                    if (res[ct++]==cand[k]) mat[k-l][u-l]=1;
                    else mat[u-l][k-l]=1;
                }
            }
            for (int k=l;k<=r;k++) {
                int coef=1;
                for (int u=l;u<=r;u++) {
                    if (k==u) continue;
                    if (!mat[k-l][u-l]) coef=0;
                }
                if (coef) tmp.push_back(cand[k]);
            }
        }
        cand=tmp;
    }
    return cand[0];
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 15
Accepted
time: 652ms
memory: 25240kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 67.5686
Acceptable Answer
time: 2618ms
memory: 90040kb

input:

1000000 20 2000000 29091473

output:

Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960
2586970244946203279
0.794925
1709116077389515223

result:

points 0.794925 Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960


Final Tests

Test #1:

score: 15
Accepted
time: 644ms
memory: 24988kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 67.5686
Acceptable Answer
time: 2607ms
memory: 82800kb

input:

1000000 20 2000000 29091471

output:

Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960
2586970244946203279
0.794925
1709116077389515223

result:

points 0.794925 Partially correct Case 2, 67 / 85, maxt = 8, maxs = 1099960