QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504788#9107. Zayin and CountFolity#AC ✓35ms3860kbC++201.6kb2024-08-04 15:59:392024-08-04 15:59:40

Judging History

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

  • [2024-08-04 15:59:40]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:3860kb
  • [2024-08-04 15:59:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __uint128_t ulll;

bool a[10],b[10];
int s[10],nb[10],ma,mb;
string X;
vector<int> digit(ulll X){
    vector<int> res;
    while(X)res.push_back(X%10),X/=10;
    return res;
}
ulll pw(ulll x,int y){
    ulll r=1;
    for(;y;y>>=1){
        if(y&1)r=r*x;
        x=x*x;
    }
    return r;
}
void solve(){
    ma=mb=0;
    for(int i=0;i<10;++i){
        cin>>a[i];
        ma+=a[i],s[i]=(i?s[i-1]:0)+a[i];
    }
    for(int i=0;i<10;++i){
        cin>>b[i];
        if(b[i])nb[mb++]=i;
    }
    cin>>X;
    vector<int> dig;
    for(char ch:X)dig.push_back(ch-'0');
    reverse(dig.begin(),dig.end());
    ulll num=0;
    for(int k=1;k<dig.size();++k){
        num+=(ma-(a[0]&&k>1))*pw(ma,k-1);
    }
    for(int k=dig.size()-1;k>=0;--k){
        num+=(s[dig[k]]-1-(a[0]&&k!=0&&k==dig.size()-1))*pw(ma,k);
    }
    //cout<<num<<'\n';
    int k=0;
    ulll sum=0;
    while(sum<=num){
        ++k;
        sum+=(mb-(b[0]&&k>1))*pw(mb,k-1);
    }
    sum-=(mb-(b[0]&&k>1))*pw(mb,k-1);
    vector<int> ans;
    //cout<<k<<' '<<(ull)sum<<'\n';
    for(int i=k-1;i>=0;--i){
        for(int j=b[0]&&i!=0&&i==k-1;j<mb;++j){
            sum+=pw(mb,i);
            if(sum>num){
                ans.push_back(nb[j]);
                break;
            }
        }
        sum-=pw(mb,i);
    }
    for(int x:ans)cout<<x;
    cout<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 3860kb

input:

10000
1 0 0 0 1 1 0 0 0 1
0 0 1 0 1 1 1 1 0 0
950595954440050004054505054050
1 0 0 0 1 1 1 1 0 0
1 1 1 0 1 0 0 0 1 1
45467007076660767550460064
1 1 1 1 0 0 0 1 0 0
1 1 0 1 1 0 1 0 0 1
23373171320213300170200722
0 0 0 0 1 1 1 0 1 0
0 0 1 0 0 1 0 1 1 1
558565664666565565558468668484
1 1 0 0 1 0 1 0 1 ...

output:

52755244567262766742575722
41990991999414091249949
101364364636933104003903
57558888789255872922852552
757222758857875785288225787822
761161760076076167101117776167
56666586555668686566656586856566686658
15611661611611111511116116661611616155
505885888775005550558080707878
3912911219633669993999199
...

result:

ok 10000 lines