QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492723#9156. 百万富翁posvii15 616ms31576kbC++141.7kb2024-07-26 15:32:412024-07-26 15:32:42

Judging History

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

  • [2024-07-26 15:32:42]
  • 评测
  • 测评结果:15
  • 用时:616ms
  • 内存:31576kb
  • [2024-07-26 15:32:41]
  • 提交

answer

#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int num[9]={2,2,62500,31248,10416,1800,120,1};
vector<int> vec;
bool vis[MAXN];
int _[1005][1005];
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.emplace_back(i),B.emplace_back(j);
            }
        }
        auto C=ask(A,B);
        for(int i=0,k=0;i<n;++i) {
            for(int j=i+1;j<n;++j) {
                _[i][j]=C[k++];
            }
        }
        int mx=0;
        for(int i=1;i<n;++i) {
            if(_[mx][i]==i) mx=i;
        }
        return mx;
    }
    else {
        for(int i=0;i<n;++i) vec.emplace_back(i);
        for(int i=0;i<8;++i) {
            vector<int> A,B;
            int k=num[i],len=vec.size();
            for(int j=0;j<len;++j) vis[j]=1;
            for(int j=0;j<k;++j) {
                for(int t=j;t<len;t+=k) {
                    for(int l=t+k;l<len;l+=k) {
                        A.emplace_back(vec[t]);
                        B.emplace_back(vec[l]);
                    }
                }
            }
            auto C=ask(A,B);
            for(int j=0,cnt=0;j<k;++j) {
                for(int t=j;t<len;t+=k) {
                    for(int l=t+k;l<len;l+=k) {
                        if(C[cnt++]==t) vis[l]=0;
                        else vis[t]=0;
                    }
                }
            }
            vector<int> tmp;
            for(int j=0;j<len;++j) {
                if(vis[j]) tmp.emplace_back(vec[j]);
            }
            vec=tmp;
        }
        return vec[0];
    }
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 15
Accepted
time: 611ms
memory: 31576kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 0
Memory Limit Exceeded

input:

1000000 20 2000000 29091473

output:

Unauthorized output

result:



Final Tests

Test #1:

score: 15
Accepted
time: 616ms
memory: 29380kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 0
Memory Limit Exceeded

input:

1000000 20 2000000 29091471

output:

Unauthorized output

result: