QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504779 | #9107. Zayin and Count | qqbb | AC ✓ | 40ms | 3824kb | C++14 | 2.5kb | 2024-08-04 15:53:47 | 2024-08-04 15:53:47 |
Judging History
answer
#include <bits/stdc++.h>
#define qqbb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define int long long
#define _ <<' '<<
#define __ <<' '
#define __l <<'\n'
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int N = 2e6 + 10, M = 4e5 + 10;
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans *= a;
a *= a;
b>>=1;
}
return ans;
}
void solve(){
vector<int> a(10),b(10);
int cnta = 0,cntb = 0;
map<int,int> mp1;
map<int,int> mp2;
map<int,int> tu;
for(int i=0;i<10;i++){
cin>>a[i];
if(a[i] == 1){
mp1[i] = cnta;
cnta++;
}
}
for(int i=0;i<10;i++){
cin>>b[i];
if(b[i] == 1){
mp2[i] = cntb;
cntb++;
tu[cntb] = i;
}
}
string s;cin>>s;
int k;
if(a[0] == 0){
k = 0;
int len = s.size();
for(int i = 1;i <= len - 1;i++){
k += qpow(cnta,i);
// cerr<<qpow(cnta,i)<<' ';
}
// cerr<<endl;
for(int i=0;i<len;i++) {
int now = s[i] - '0';
k += mp1[now] * qpow(cnta,len-i-1);
// cerr<<mp1[now] * qpow(cnta,len-i-1)<<' ';
}
// k++;
}
else{
k = 0;
int len = s.size();
k += cnta;
for(int i = 2;i <= len -1;i++){
k += qpow(cnta, i - 1) *(cnta - 1);
}
k += (mp1[s[0]-'0'] - 1) * qpow(cnta,len - 1);
for(int i=1;i<len;i++) {
int now = s[i] - '0';
k += mp1[now] * qpow(cnta,len-i-1);
// cerr<<mp1[now] * qpow(cnta,len-i-1)<<' ';
}
// k++;
}
// cout<<k<<endl;
if(k <= cntb && a.size() == 1){
cout<<tu[k];
return;
}
int k1,deg;
if (b[0] == 0){
k1=0;
for(int i = 1;i <= 100;i++){
if(k1 + qpow(cntb,i) > k){
deg = i;
break;
}
k1 += qpow(cntb,i);
}
int res = k - k1;
for(int i=deg; i>=1;i--){
int tmp = res / qpow(cntb,i-1);
// cout<<res _ tmp _ qpow(cntb,i) __l;
res -= tmp * qpow(cntb,i-1);
cout<<tu[tmp + 1];
}
}
else{
k1 = 0;
k1 += cntb;
if(k1 > k) deg = 1;
for(int i = 2;i <= 100;i++){
if(k1 + qpow(cntb,i-1)*(cntb-1)> k){
deg = i;
break;
}
k1 += qpow(cntb,i-1)*(cntb-1);
}
int res = k - k1;
int tmp = res / qpow(cntb,deg - 1);
cout<<tu[tmp+2];
res -= tmp * qpow(cntb,deg - 1);
for(int i=deg - 1; i>=1;i--){
int tmp = res / qpow(cntb,i-1);
// cout<<res _ tmp _ qpow(cntb,i) __l;
res -= tmp * qpow(cntb,i-1);
cout<<tu[tmp + 1];
}
}
cout<<endl;
}
signed main(){
qqbb;
// cout<<fixed<<setprecision(0);
int Test=1;
cin>>Test;
while(Test--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 40ms
memory: 3824kb
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