QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32608#885. Keep Calm And Carry OffFroggyguaWA 3ms3656kbC++1710.0kb2022-05-22 11:55:172022-05-22 11:55:20

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:55:20]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3656kb
  • [2022-05-22 11:55:17]
  • 提交

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=1,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: 3556kb

input:

10
99

output:

1

result:

ok answer is '1'

Test #2:

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

input:

90
10

output:

10

result:

ok answer is '10'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

23425
487915

output:

12085

result:

ok answer is '12085'

Test #4:

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

input:

1
1

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

99
99

output:

1

result:

ok answer is '1'

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 3616kb

input:

14
86

output:

0

result:

wrong answer expected '14', found '0'