QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32609#885. Keep Calm And Carry OffFroggyguaAC ✓73ms40108kbC++1710.0kb2022-05-22 11:56:202022-05-22 11:56:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-22 11:56:21]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:40108kb
  • [2022-05-22 11:56:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
enum multiply_tag{
    brute_tag,fft_tag,mix_tag
};
struct Complex{
    double x,y;
    Complex(double _x=0,double _y=0){x=_x,y=_y;}
    friend Complex operator + (const Complex &a,const Complex &b){
        return Complex(a.x+b.x,a.y+b.y);
    }
    friend Complex operator - (const Complex &a,const Complex &b){
        return Complex(a.x-b.x,a.y-b.y);
    }
    friend Complex operator * (const Complex &a,const Complex &b){
        return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
    }
};
template<int L>
class Poly_fft{
    using poly=Poly_fft<L>;
    static constexpr double PI=acos(-1.0);
    vector<Complex> f;
    struct initializer{
        vector<Complex> GG[2][L+1];
        initializer(){
            for(int p=1;p<=L;++p){
                Complex buf1(cos(2*PI/(1<<p)),sin(2*PI/(1<<p)));
                Complex buf0(cos(2*PI/(1<<p)),-sin(2*PI/(1<<p)));
                GG[0][p].resize(1<<p);
                GG[1][p].resize(1<<p);
                GG[0][p][0]=GG[1][p][0]=Complex(1,0);
                for(int i=1;i<(1<<p);++i){
                    GG[0][p][i]=GG[0][p][i-1]*buf0;
                    GG[1][p][i]=GG[1][p][i-1]*buf1;
                }
            }
        }
    };
    static initializer init;
    static vector<int> tr;
    static int FFT_init(int n){
        int lim=1;
        while(lim<n)lim<<=1;
        tr.resize(lim);
        for(int i=0;i<lim;++i){
            tr[i]=((tr[i>>1]>>1)|(i&1?lim>>1:0));
        }
        return lim;
    }
    static void FFT(poly &A,int flag,int n){
        A.resize(n);
        for(int i=0;i<n;++i){
            if(i<tr[i])swap(A.f[i],A.f[tr[i]]);
        }
        for(int p=2,j=1;p<=n;p<<=1,++j){
            int len=p>>1;
            for(int k=0;k<n;k+=p){
                auto buf=init.GG[flag][j].begin();
                for(int i=k;i<k+len;++i,++buf){
                    Complex tmp=(*buf)*A.f[i+len];
                    A.f[i+len]=A.f[i]-tmp;
                    A.f[i]=A.f[i]+tmp;  
                }
            }   
        }
        if(!flag){
            for(int i=0;i<n;++i){
                A.f[i].x=A.f[i].x/n;
            }   
        }
    }
public:
    Poly_fft(const vector<Complex> &_f):f(_f){}
    Poly_fft(){}
    Poly_fft(int _n){f.resize(_n);}
    int size(){return f.size();}
    void resize(int _n){f.resize(_n);}
    vector<Complex>::reference operator [] (int x){
        return f[x];
    }
    friend poly Mul(poly A,poly B){
        int n=A.size()+B.size()-1;
        int lim=FFT_init(n);
        poly C(lim);
        FFT(A,1,lim),FFT(B,1,lim);
        for(int i=0;i<lim;++i){
            C[i]=A[i]*B[i];
        }
        FFT(C,0,lim);
        C.resize(n);
        return C;
    }
};
template<int L>
typename Poly_fft<L>::initializer Poly_fft<L>::init;
template<int L>
vector<int> Poly_fft<L>::tr;
using poly=Poly_fft<20>;
/*
进制,压位长度,乘法方式
*/
template<int H,int D,multiply_tag mtag>          
class unsigned_bigint{
    using bint=unsigned_bigint<H,D,mtag>;
    static constexpr int B=round(pow(H,D));
    vector<int> g;
public:
    unsigned_bigint(const vector<int> &_g):g(_g){}
    unsigned_bigint(int x=0){
        if(!x){g.resize(1);return;}
        while(x)g.push_back(x%B),x/=B;  
    }
    unsigned_bigint(string s){
        g.resize(((int)s.length()+D-1)/D);
        reverse(s.begin(),s.end());
        for(int i=0;i*D<(int)s.length();++i){
            for(int j=min(D,(int)s.length()-i*D)-1;j>=0;--j){
                g[i]=g[i]*H+s[i*D+j]-'0';
            }
        }   
    }
    int length(){
        int len=D*(g.size()-1);
        int x=g.back();
        while(x)x/=H,++len;
        return max(1,len);
    }
    void Del(){
        g.pop_back();
        if(g.empty())g.push_back(0);
    }
    bint &operator += (const bint &b){
        if(b.g.size()>g.size())g.resize(b.g.size());
        g.push_back(0);
        for(int i=0;i<(int)g.size();++i){
            if(i<(int)b.g.size())g[i]+=b.g[i];
            if(g[i]>=B)++g[i+1],g[i]-=B;    
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator -= (const bint &b){
        if(b.g.size()>g.size())g.resize(b.g.size());
        g.push_back(0);
        for(int i=0;i<(int)g.size();++i){
            if(i<(int)b.g.size())g[i]-=b.g[i];
            if(g[i]<0)--g[i+1],g[i]+=B; 
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator *= (const bint &b){
        vector<ll> tmp;
        if(mtag==brute_tag||(mtag==mix_tag&&1LL*g.size()*b.g.size()<=1e7)){
            tmp.resize(g.size()+b.g.size());
            for(int i=0;i<(int)g.size();++i){
                for(int j=0;j<(int)b.g.size();++j){
                    tmp[i+j]+=1LL*g[i]*b.g[j];  
                }
            }
            g.resize(g.size()+b.g.size());
        }
        else{
            poly F(g.size()),G(b.g.size());
            for(int i=0;i<(int)F.size();++i)F[i].x=g[i];
            for(int i=0;i<(int)G.size();++i)G[i].x=b.g[i];
            F=Mul(F,G);
            g.resize(F.size()+1);
            tmp.resize(F.size()+1);
            for(int i=0;i<(int)F.size();++i){
                tmp[i]=round(F[i].x);
            }
        }
        for(int i=0;i<(int)tmp.size();++i){
            g[i]=tmp[i]%B;
            if(tmp[i]>=B)tmp[i+1]+=tmp[i]/B;
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator /= (const bint &b){
        if(b.g.size()>g.size()){
            g=vector<int>(1);
        }
        else{
            bint a;
            a.g.resize(g.size()-b.g.size()+1);
            for(int i=g.size()-b.g.size();i>=0;--i){
                bint tmp(vector<int>(g.begin()+i,g.end()));
                g.erase(g.begin()+i,g.end());
                int l=0,r=B;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(bint(mid)*b<=tmp){
                        a.g[i]=mid;
                        l=mid+1;
                    }
                    else{
                        r=mid;
                    }
                }
                tmp-=a.g[i]*b;
                if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
            }
            g=a.g;
            while(g.size()>1&&!g.back())g.pop_back();
            /*
            bint a;
            a.g.resize(g.size()-b.g.size()+1);
            for(int i=g.size()-b.g.size();i>=0;--i){
                bint tmp(vector<int>(g.begin()+i,g.end()));
                g.erase(g.begin()+i,g.end());
                while(tmp>=b){
                    tmp-=b,++a.g[i];
                }
                if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
            }
            g=a.g;
            while(g.size()>1&&!g.back())g.pop_back();
            */
        }
        return *this;
    }
    bint &operator %= (const bint &b){
        (*this)=(*this)-(*this)/b*b;
        return *this;
    }
    bint Pow(int b){
        bint ans(1);
        int k=0;
        while(b>=(1<<k))++k;
        for(int i=k-1;i>=0;--i){
            ans=ans*ans;
            if(b>>i&1)ans=ans*(*this);
        }
        return ans;
    }
    friend bint operator + (const bint &a,const bint &b){
        return bint(a)+=b;
    }
    friend bint operator - (const bint &a,const bint &b){
        return bint(a)-=b;
    }
    friend bint operator * (const bint &a,const bint &b){
        return bint(a)*=b;
    }
    friend bint operator / (const bint &a,const bint &b){
        return bint(a)/=b;
    }
    friend bint operator % (const bint &a,const bint &b){
        return bint(a)%=b;
    }
    friend bool operator == (const bint &a,const bint &b){
        return a.g==b.g;
    }
    friend bool operator != (const bint &a,const bint &b){
        return !(a.g==b.g);
    }
    friend bool operator < (const bint &a,const bint &b){
        if(a.g.size()<b.g.size())return true;
        if(a.g.size()>b.g.size())return false;
        for(int i=a.g.size()-1;i>=0;--i){
            if(a.g[i]<b.g[i])return true;
            if(a.g[i]>b.g[i])return false;
        }
        return false;
    }
    friend bool operator > (const bint &a,const bint &b){
        return b<a;
    }
    friend bool operator <= (const bint &a,const bint &b){
        return !(a>b);
    }
    friend bool operator >= (const bint &a,const bint &b){
        return !(a<b);
    }
    friend ostream &operator << (ostream &out,const bint &a){
        string s="";
        if(!a.g.back())s="0";
        else{
            int x=a.g.back();
            while(x)s+=x%10+'0',x/=10;
            reverse(s.begin(),s.end());
        }
        out<<s;
        for(int i=(int)a.g.size()-2;i>=0;--i){
            s="";
            int x=a.g[i];
            for(int j=0;j<D;++j){
                s+=x%10+'0',x/=10;
            }
            reverse(s.begin(),s.end());
            out<<s; 
        }
        return out;
    }
};
using bint=unsigned_bigint<10,1,mix_tag>;
#define N 1000010
string a,b;
int n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b;
	n=a.length(),m=b.length();
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	int las=-1;
	for(int i=0,op=0;i<max(n,m);++i){
		int x=(i>=n?0:a[i]-'0')+(i>=m?0:b[i]-'0')+op;
		if(x>=10){
			op=1;
			las=i;
		}
		else{
			op=0;
		}
	}
	if(las<0){
		cout<<0<<'\n';
		return 0;
	}
	string _a=a,_b=b;
	for(int i=0;i<=las;++i){
		if(_a.length()<=i)_a.push_back('0');
		_a[i]='0';
	}
	if(_a.length()<=las+1)_a.push_back('0');
	++_a[las+1];
	for(int i=0;i<=las;++i){
		if(_b.length()<=i)_b.push_back('0');
		_b[i]='0';
	}
	if(_b.length()<=las+1)_b.push_back('0');
	++_b[las+1];
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	reverse(_a.begin(),_a.end());
	reverse(_b.begin(),_b.end());
	cout<<min(bint(_a)-bint(a),bint(_b)-bint(b))<<'\n';
	return 0;
}



詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3500kb

input:

10
99

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

90
10

output:

10

result:

ok answer is '10'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

23425
487915

output:

12085

result:

ok answer is '12085'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1
1

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

99
99

output:

1

result:

ok answer is '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

14
86

output:

14

result:

ok answer is '14'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

899999999999999999999
100000000000000000001

output:

100000000000000000001

result:

ok answer is '100000000000000000001'

Test #8:

score: 0
Accepted
time: 50ms
memory: 40108kb

input:

615357649595284099508435993883986571313695656691562389866620971630644953030429613681442060702023197532680463771166724257258948140032009435767225187778914625685600736964207275868974321513156027752788270804733647164380664571327109020774746630643814103150883559720458844636326901760106285413007100737536...

output:

226164757855375706179130034126837577710545348626568907238536520434546544085882446273981029021778063112888523241983297218947698252532826120194967039881313867888258883810876610793168815193851023510269144054457285631520878535365581681349042349672439715344120755176307571379581412256786498122023796566813...

result:

ok answer is '226164757855375706179130034126...1032113015742081980588406310856'

Test #9:

score: 0
Accepted
time: 0ms
memory: 5536kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0

result:

ok answer is '0'

Test #10:

score: 0
Accepted
time: 73ms
memory: 38840kb

input:

946678535444896475642225008527348253117127344137446723931302495407581979054231432196768653557235697280697999349345542859864503525832718970888297969471590384454809084105146882526427617822167077225221683317423530502375438306992125794196668936915418103664819269986191955766257534524689071638219238188976...

output:

533214645551035243577749914726517468828726558625532760686975045924180209457685678032313464427643027193020006506544571401354964741672810291117020305284096155451909158948531174735723821778329227747783166825764694976245616930078742058033310630845818963351807300138080442337424654753109283617807618110239...

result:

ok answer is '533214645551035243577749914726...8583282299712982139175537021362'

Test #11:

score: 0
Accepted
time: 41ms
memory: 39168kb

input:

794946477760061325408107597512810946289384941381736255316518687888511341258007534679058032849319730631613743099733353038802970355718221088259886925518970281655634779851495550264110452025361079238655051609110357880450805087197804035613307707314768911650131971835865731706270390379379832722335057330470...

output:

205053522239938674591892402487189053710615058618263744683481312111488658741992465320941967150680269368386256900266646961197029644281778911740113074481029718344365220148504449735889547974638920761344948390889642119549194912802195964386692292685231088349868028164134268293729609620620167277664942669529...

result:

ok answer is '205053522239938674591892402487...4895693158694032335924691582580'

Test #12:

score: 0
Accepted
time: 42ms
memory: 39516kb

input:

740396512715746854480688476727726843695909844190398984187893683516689175082139997856915168192558523514785642438089549764358594098561796813209038321522889191781035343854374929109665898552729746770608711636305055090924461862639090335815510632703670463147194228154033606862279586041022594067305712355803...

output:

259603487284253145519311523272273156304090155809601015812106316483310824917860002143084831807441476485214357561910450235641405901438203186790961678477110808218964656145625070890334101447270253229391288363694944909075538137360909664184489367296329536852805771845966393137720413958977405932694287644196...

result:

ok answer is '259603487284253145519311523272...7124298880143408010404228204895'

Test #13:

score: 0
Accepted
time: 34ms
memory: 39036kb

input:

808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080...

output:

191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919...

result:

ok answer is '191919191919191919191919191919...9191919191919191919191919191920'

Test #14:

score: 0
Accepted
time: 11ms
memory: 35596kb

input:

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 53ms
memory: 38204kb

input:

888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok answer is '111111111111111111111111111111...1111111111111111111111111111112'

Test #16:

score: 0
Accepted
time: 41ms
memory: 39760kb

input:

499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

result:

ok answer is '499999999999999999999999999999...9999999999999999999999999999999'

Test #17:

score: 0
Accepted
time: 56ms
memory: 38608kb

input:

902851346436306806616375942396607826120232155242259147614243592903405735290837981154314613604373937058180635157768204138128396693345023355887820571704408856138693881765209464570723015717187118417699724996521322468835282812828545349457610944807873712140962669646920063042802116551616341958682221180684...

output:

739784808063119079929960519131554991813736147608454624748722101820388330144313273774081346945197605998068619643008000320015228364440867297627844532995103260191004283851259488125663821507594499196247233749377082143689851535156330319615505969268510443807604553524147479720718432743772029026906290480988...

result:

ok answer is '739784808063119079929960519131...1948627624188898000206620879303'

Test #18:

score: 0
Accepted
time: 37ms
memory: 39640kb

input:

724416096404218447265833382721297139425723348230646412938535112399662200961459489276744159193709343615237043403451777684608176033864123303353042148426141106174503987074111702253415957879317805779143259309953292187561544285879213401013240932738394155151275424316854703682327362480740497418303833476481...

output:

275583903595781552734166617278702860574276651769353587061464887600337799038540510723255840806290656384762956596548222315391823966135876696646957851573858893825496012925888297746584042120682194220856740690046707812438455714120786598986759067261605844848724575683145296317672637519259502581696166523518...

result:

ok answer is '275583903595781552734166617278...8872930707584800540407644105638'

Test #19:

score: 0
Accepted
time: 38ms
memory: 39316kb

input:

179760883913929098769751954947190783986510762079451401291657475628833258870415316784826579026164324281062020081021320517742313824799906611937368746321612306269758496471784982997262378087781498524472377305471180347632989650011243499867679056925218306140508787728196557041840793032875464254908876021669...

output:

202391160860709012302480450528092160134892379205485987083425243711667411295846832151734209738356757189379799189786794822576861752000933880626312536783876937302415035282150170027376219122185014755276226945288196523670103499887565001323209430747816938594912122718034429581592069671245357450911239783305...

result:

ok answer is '202391160860709012302480450528...2823656215559711050462000001286'

Test #20:

score: 0
Accepted
time: 29ms
memory: 39048kb

input:

694093295978385763996081646122651163487393563403375307120640726515101625170981544132833099306255215328986417862623494481857751894930538664304406593098107350723363635953635761495109280467562145123198911580622745275722840557806514156432129827761280709147879094131413817732889425551527261432195522728058...

output:

255769660772460029135659150462029009323862269154134965970617506744888571963168440708845854207631866982569513435894446504364418923339414859467991484536976751318428793008155206466142281148699553779149059558262299962485591410811078329484901571300035768990820396518084796670337233215816256442433385117841...

result:

ok answer is '255769660772460029135659150462...5240882786975575043401117211469'

Test #21:

score: 0
Accepted
time: 42ms
memory: 39432kb

input:

300681870704322241560104970320057811567211737552516811385136323064072671173825819427397761947835599467617616151523159779966244586152970280628373138993914850714409848595061132786328706497489992388484505984334528900604134964071443214035814375461628216063519758155475552005548598916806141612427038578006...

output:

245470701274362774449400345544121088380094571024237326765419310035541831084665407865334639554935227551147676469232950570285818569364395955422076452513852795266969401671952897250009875595788582424670890141940295697590000618374944180311423441095906635772223869242769402714599365582728097188947527241436...

result:

ok answer is '245470701274362774449400345544...4786420933984638221599280514231'