QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#12500 | #682. Stickers | Oganesson | 100 ✓ | 130ms | 9844kb | C++20 | 5.4kb | 2021-08-06 17:09:13 | 2022-05-18 03:24:24 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
namespace IO
{
const int sz=1<<15;
char inbuf[sz],outbuf[sz];
char *pinbuf=inbuf+sz;
char *poutbuf=outbuf;
inline char _getchar()
{
if (pinbuf==inbuf+sz)fread(inbuf,1,sz,stdin),pinbuf=inbuf;
return *(pinbuf++);
}
inline void _putchar(char x)
{
if (poutbuf==outbuf+sz)fwrite(outbuf,1,sz,stdout),poutbuf=outbuf;
*(poutbuf++)=x;
}
inline void flush()
{
if (poutbuf!=outbuf)fwrite(outbuf,1,poutbuf-outbuf,stdout),poutbuf=outbuf;
}
}
inline int read(){
int v=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
v=v*10+c-'0';
c=getchar();
}
return v*f;
}
const int Maxn=155;
const int Bl=100000000;
const int W=8;
struct BigInt{
int val[20];
bool neg;
BigInt(){
memset(val,0,sizeof(val));
neg=0;
}
BigInt(int v){
memset(val,0,sizeof(val));
neg=0;
val[0]=v;
}
void Clear(){
memset(val,0,sizeof(val));
neg=0;
}
bool operator <(const BigInt &B)const{
if (neg!=B.neg){
return neg>B.neg;
}
for (int i=19;i>=0;i--){
if (val[i]!=B.val[i]){
return neg^(val[i]<B.val[i]);
}
}
return 0;
}
void Add(BigInt B){
if (!neg && !B.neg){
for (int i=0;i<20;i++){
val[i]+=B.val[i];
if (val[i]>=Bl){
val[i]-=Bl;val[i+1]++;
}
}
}
else if (!neg && B.neg){
B.neg^=1;
if (this->operator<(B)){
for (int i=0;i<20;i++){
val[i]=B.val[i]-val[i];
if (val[i]<0){
val[i]+=Bl;
B.val[i+1]--;
}
}
neg^=1;
}
else{
for (int i=0;i<20;i++){
val[i]-=B.val[i];
if (val[i]<0){
val[i]+=Bl;
val[i+1]--;
}
}
}
}
else if (neg && !B.neg){
neg^=1;
if (B<(*this)){
for (int i=0;i<20;i++){
val[i]-=B.val[i];
if (val[i]<0){
val[i]+=Bl;
val[i+1]--;
}
}
neg^=1;
}
else{
for (int i=0;i<20;i++){
val[i]=B.val[i]-val[i];
if (val[i]<0){
val[i]+=Bl;
B.val[i+1]--;
}
}
}
}
else{
for (int i=0;i<20;i++){
val[i]+=B.val[i];
if (val[i]>=Bl){
val[i]-=Bl;val[i+1]++;
}
}
}
}
void Del(BigInt B){
bool FZ=1;
for (int i=0;i<20;i++) FZ&=(B.val[i]==0);
if (FZ) return;
B.neg^=1;
Add(B);
}
void Mul(int k){
for (int i=19;i>=0;i--){
val[i]=val[i]*k;
if(val[i]>=Bl){
val[i+1]+=val[i]/Bl;
val[i]%=Bl;
}
}
}
void Out(){
int p=-1;
for (int i=19;i>=0;i--){
if (val[i]){
p=i;
break;
}
}
if (p==-1){
printf("0\n");
return;
}
if (neg){
putchar('-');
}
printf("%d",val[p]);
for (int i=p-1;i>=0;i--){
assert(val[i]>=0 && val[i]<Bl);
printf("%.8d",val[i]);
}
printf("\n");
}
};
BigInt min(BigInt A,BigInt B){
return (A<B)?A:B;
}
BigInt F[Maxn][Maxn],G[Maxn][Maxn],S[Maxn][Maxn],Ept;
BigInt PW[Maxn];
int a[10],D;
bool bad;
BigInt Qr(int x,int y,BigInt V,int f=0){
// first less than V
if (!(G[x][y]<V)){
bad=true;
return BigInt(0);
}
if (BigInt(0)<V && f) return BigInt(0);
if (x==0){
if (BigInt(0)<V) return BigInt(0);
else return BigInt(1);
}
BigInt SS,CP;
for (int i=0;i<10;i++){
BigInt tmp=SS;
tmp.Add(G[x-1][y+(i==D)]);
if (tmp<V && (f||i)){
V.Del(SS);
BigInt PS=Qr(x-1,y+(i==D),V,1);
PS.Add(CP);
return PS;
}
CP.Add(PW[x-1]);
SS.Add(S[x-1][y+(i==D)]);
}
bad=true;
}
BigInt Get(int d,int A){
D=d;
for (int i=0;i<Maxn;i++){
for (int j=0;j<Maxn;j++){
F[i][j].Clear();G[i][j].Clear();S[i][j].Clear();
}
}
for (int i=0;i<Maxn;i++){
S[0][i].val[0]=A-i;
if (S[0][i].val[0]<0){
S[0][i].val[0]*=-1;
S[0][i].neg=1;
}
G[0][i]=S[0][i];
F[0][i].val[0]=1;
}
BigInt bas;
bas.val[0]=1;
for (int i=1;i<Maxn;i++){
for (int j=0;j<Maxn;j++){
if (i+j>=Maxn) continue;
BigInt MnV,Pos,CP,tot;
MnV.val[19]=11451419;
for (int k=0;k<10;k++){
BigInt CS=tot;CS.Add(G[i-1][j+(k==d)]);
if (CS<MnV){
MnV=CS;
Pos=CP;Pos.Add(F[i-1][j+(k==d)]);
}
tot.Add(S[i-1][j+(k==d)]);
CP.Add(bas);
}
S[i][j]=tot;
G[i][j]=MnV;
F[i][j]=Pos;
}
bas.Mul(10);
}
//F[5][1].Out();G[5][1].Out();
if (d){
for (int i=1;i<Maxn;i++){
bad=false;
BigInt tt=Qr(i,0,A,0);
if (!bad){
return tt;
}
}
}
else{
BigInt fuck(A);
fuck.Del(PW[0]);
for (int i=1;i<Maxn;i++){
bad=false;
BigInt tt=Qr(i,0,fuck,0);
if (!bad){
return tt;
}
fuck.Del(PW[i]);
}
assert(false);
}
}
int main(){
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
/*
int cnt=0;
for (int i=1;;i++){
cnt++;
int j=i;
while (j){
if (j%10==4) cnt--;
j/=10;
}
if (cnt<0){
cerr<<i<<endl;
return 0;
}
}*/
PW[0].val[0]=1;
for (int i=1;i<Maxn;i++) PW[i]=PW[i-1],PW[i].Mul(10);
//for (int i=0;i<Maxn;i++) PW[i].Out();
//return 0;
for (int i=0;i<10;i++){
scanf("%d",&a[i]);
//a[i]=1;
}
BigInt Ans;
Ans.val[19]=11451419;
for (int i=0;i<10;i++){
BigInt tmp=Get(i,a[i]);
//cerr<<i<<endl;
//tmp.Out();
if (tmp<Ans){
Ans=tmp;
}
}
Ans.Del(BigInt(1));
Ans.Del(BigInt(1));
Ans.Out();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 9.09091
Accepted
time: 129ms
memory: 9740kb
input:
1 2 1 1 1 1 1 1 1 1
output:
28263827
result:
ok single line: '28263827'
Test #2:
score: 9.09091
Accepted
time: 121ms
memory: 9828kb
input:
1 2 1 1 1 1 1 1 1 1
output:
28263827
result:
ok single line: '28263827'
Test #3:
score: 9.09091
Accepted
time: 130ms
memory: 9716kb
input:
1 2 2 2 2 1 1 1 1 1
output:
5555555554
result:
ok single line: '5555555554'
Test #4:
score: 9.09091
Accepted
time: 124ms
memory: 9756kb
input:
2 2 2 2 2 2 2 2 2 2
output:
1999919999999980
result:
ok single line: '1999919999999980'
Test #5:
score: 9.09091
Accepted
time: 123ms
memory: 9844kb
input:
4 3 2 2 2 2 2 2 2 3
output:
282638284722222221
result:
ok single line: '282638284722222221'
Test #6:
score: 9.09091
Accepted
time: 125ms
memory: 9724kb
input:
2 4 3 3 3 3 3 3 3 3
output:
1005594043670359641774
result:
ok single line: '1005594043670359641774'
Test #7:
score: 9.09091
Accepted
time: 130ms
memory: 9772kb
input:
4 4 4 4 4 4 3 3 3 3
output:
666666666666666666666666666665
result:
ok single line: '666666666666666666666666666665'
Test #8:
score: 9.09091
Accepted
time: 126ms
memory: 9784kb
input:
4 5 5 5 5 5 7 8 9 9
output:
100559404367035964177652825361730559404364
result:
ok single line: '100559404367035964177652825361730559404364'
Test #9:
score: 9.09091
Accepted
time: 123ms
memory: 9800kb
input:
6 6 6 6 5 5 5 5 5 5
output:
4999999949999999994999999999499999999949999999953
result:
ok single line: '4999999949999999994999999999499999999949999999953'
Test #10:
score: 9.09091
Accepted
time: 124ms
memory: 9664kb
input:
7 8 8 7 7 7 7 7 7 7
output:
371599993999999999399999999939999999993999999999399999999939999999938
result:
ok single line: '371599993999999999399999999939...3999999999399999999939999999938'
Test #11:
score: 9.09091
Accepted
time: 129ms
memory: 9672kb
input:
9 9 9 9 9 9 9 9 9 9
output:
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
result:
ok single line: '199991999999999199999999919999...1999999999199999999919999999918'