QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262767#885. Keep Calm And Carry OffFyindCompile Error//Python38.6kb2023-11-23 23:25:462023-11-23 23:25:48

Judging History

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

  • [2023-11-23 23:25:48]
  • 评测
  • [2023-11-23 23:25:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 2e5 + 35;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

template<size_t siz>
struct Bitset {
    typedef unsigned long long ull;
    static const int N = (siz+63)/64;
    ull A[N] = {};
    ull AF = -1ull;
    ull base = 1ull<<63;
    int cnt = 0;
    Bitset(int k=0) { A[0] = k; cnt = __builtin_popcount(k); }
    Bitset& operator|=(const Bitset& rhs) {
        cnt = 0;
        for (int i = 0;i < N; ++i) A[i] |= rhs.A[i], cnt += __builtin_popcountll(A[i]);
        return *this; 
    }
    Bitset& operator&=(const Bitset& rhs) {
        cnt = 0;
        for (int i = 0;i < N; ++i) A[i] &= rhs.A[i],cnt += __builtin_popcountll(A[i]);
        return *this; 
    }
    Bitset& operator^=(const Bitset& rhs) {
        cnt = 0;
        for (int i = 0;i < N; ++i) A[i] ^= rhs.A[i], cnt += __builtin_popcountll(A[i]);
        return *this; 
    }
    Bitset operator~() const {
        Bitset ret = *this;
        ret.cnt = siz - cnt;
        for (int i = 0;i < N; ++i) ret.A[i] = ~A[i];
        return ret; 
    }
    size_t size() const {
        return siz;
    }
    bool any() const {
        return cnt;
    }
    bool none() const {
        return !cnt;
    }
    int count() const {
        return cnt;
    }
    int clz() const {
        for (int i = N-1;i >= 0; --i) {
            if (A[i]) return i*64+63 - __builtin_clzll(A[i]);
        }
        return -1;
    }
    int ctz() const {
        for (int i = 0;i < N; ++i) {
            if (A[i]) return i*64 + __builtin_ctzll(A[i]);
        }
        return -1;
    }
    Bitset& operator<<=(int k) {
        k = min(k, (int)siz);
        int d = k>>6, r = k&63;
        cnt = 0;
        for (int i = N-1;i >= d; --i) A[i] = A[i-d];
        for (int i = 0;i < d; ++i) A[i] = 0;
        for (int i = N-1;i >= 1; --i) {
            A[i] <<= r;
            A[i] |= A[i-1]>>(64-r);
            cnt += __builtin_popcountll(A[i]);
        }
        A[0] <<= r;
        cnt += __builtin_popcountll(A[0]);
        return *this;
    }
    Bitset& operator>>=(int k) {
        k = min(k, (int)siz);
        cnt = 0;
        int d = k>>6, r = k&63;
        ll base = (1ull<<r)-1;
        for (int i = 0;i < N-d; ++i) A[i] = A[i+d];
        for (int i = N-1;i >= N-d; --i) A[i] = 0;
        for (int i = 0;i < N-1; ++i) {
            A[i] >>= r;
            A[i] |= (A[i+1] & base) << (64-r);
            cnt += __builtin_popcountll(A[i]);
        }
        A[N-1] >>= r;
        cnt += __builtin_popcountll(A[N-1]);
        return *this;
    }
    Bitset& operator+=(const Bitset &rhs) {
        char c = 0;
        cnt = 0;
        int mx = N;
        int mx2 = clz(), mx3 = rhs.clz();
        mx = min(mx, max(mx2+1, mx3+1));
        for (int i = 0;i < mx; ++i) {
            if (!c && !rhs.A[i]) {
                cnt += __builtin_popcountll(A[i]); 
                continue;
            }
            char nc = 0;
            ull ri = rhs.A[i];
            if (A[i] & base) {
                nc++;
                A[i] ^= base;
            }
            if (ri & base) {
                nc++;
                ri ^= base;
            }
            A[i] += ri + c;
            if (A[i] & base) {
                nc++;
                A[i] ^= base;
            }
            if (nc >= 2) {
                c = 1;
                nc -= 2;
            } else c = 0;
            if (nc) A[i] += base;
            cnt += __builtin_popcountll(A[i]); 
        }
        return *this;
    }
    Bitset& operator-=(const Bitset &rhs) {
        char c = 0;
        cnt = 0;
        int mx = N;
        int mx2 = clz();
        mx = min(mx, mx2+1);
        for (int i = 0;i < mx; ++i) {
            if (!c && !rhs.A[i]) {
                cnt += __builtin_popcountll(A[i]); 
                continue;
            }
            char nc = 0;
            ull ri = rhs.A[i];
            if (!(A[i] & base)) {
                A[i] ^= base;
                nc++;
            }
            if (ri & base) {
                ri ^= base;
                nc++;
            }
            A[i] -= ri + c;
            if (nc && A[i] & base) {
                nc--;
                A[i] ^= base;
            }
            if (nc >= 1) {
                if (nc < 2) A[i] ^= base;
                c = 1;
            } else c = 0;
            cnt += __builtin_popcountll(A[i]); 
        }
        return *this;
    }
    bool operator==(const Bitset& rhs) const {
        bool ret = 1;
        for (int i = 0;i < N; ++i) ret &= A[i] == rhs.A[i];
        return ret;
    }
    bool operator==(const int x) const {
        if (!x) return none();
        return *this == Bitset(x);
    }
    char operator[](const int k) const {
        return A[k>>6]>>(k&63)&1;
    }
    bool test(const int k) {
        return (*this)[k];
    }
    void set(const int k) {
        int p = k>>6;
        cnt -= __builtin_popcountll(A[p]);
        A[p] |= 1ull << (k&63);
        cnt += __builtin_popcountll(A[p]);
    }
    void set(const int k, const int v) {
        if (test(k) != v) A[k>>6] ^= 1ull << (k&63), cnt += v ? 1 : -1;
    }
    friend Bitset operator|(const Bitset &lhs, const Bitset &rhs) {
        Bitset res = lhs;
        res |= rhs;
        return res;
    }
    friend Bitset operator&(const Bitset &lhs, const Bitset &rhs) {
        Bitset res = lhs;
        res &= rhs;
        return res;
    }
    friend Bitset operator^(const Bitset &lhs, const Bitset &rhs) {
        Bitset res = lhs;
        res ^= rhs;
        return res;
    }
    friend Bitset operator<<(const Bitset &lhs, const int k) {
        Bitset res = lhs;
        res <<= k;
        return res;
    }
    friend Bitset operator>>(const Bitset &lhs, const int k) {
        Bitset res = lhs;
        res >>= k;
        return res;
    }
    friend Bitset operator+(const Bitset &lhs, const Bitset &rhs) {
        Bitset res = lhs;
        res += rhs;
        return res;
    }
    friend Bitset operator-(const Bitset &lhs, const Bitset &rhs) {
        Bitset res = lhs;
        res -= rhs;
        return res;
    }
    friend ostream &operator<<(std::ostream &os, const Bitset &a) {
        for (int i = N-1;i >= 0; --i) {
            for (int j = 63;j >= 0; --j) if (i*64+j < siz){
                if (a.A[i]>>j & 1) os << "1";
                else os << "0";
            }
        }
        return os;
    }

    ull toull() {
        return A[0];
    }
};
typedef Bitset<maxn> Bint;

bool operator <(const Bint &a,const Bint &b){
    for (int i=a.size()-1;i>=0;--i)
        if (a[i]!=b[i])return a[i]<b[i];
    return 0;
}
bool operator >(const Bint &a,const Bint &b){return b<a;}
bool operator <=(const Bint &a,const Bint &b){return !(b<a);}
bool operator >=(const Bint &a,const Bint &b){return !(a<b);}
Bint operator -(const Bint &a){return Bint(1)+~a;}
Bint operator *(Bint a,Bint b){
    Bint r(0);
    for (;b.any();b>>=1,a<<=1)
        if (b[0])r+=a;
    return r;
}
Bint& operator *=(Bint &a,const Bint &b){return a=a*b;}
pair<Bint,Bint> divide(Bint a,const Bint &b){
    Bint c=0; int i=0;
    while ((b<<(i+1))<=a)++i;
    for (;i>=0;--i)
        if (a>=(b<<i))a-=b<<i,c.set(i,1);
    return make_pair(c,a);
}
Bint operator /(const Bint &a,const Bint &b){return divide(a,b).first;}
Bint& operator /=(Bint &a,const Bint &b){return a=a/b;}
Bint operator %(const Bint &a,const Bint &b){return divide(a,b).second;}
Bint& operator %=(Bint &a,const Bint &b){return a=a%b;}
inline void read(Bint &x){
    char ch;int bo=0; x=0;
    for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
    for (;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar());
    if (bo)x=-x;
}
inline void print(Bint x){
    vector<Bint> v;
    if (x==0)printf("0");
    for (Bint y=1;y<=x;y*=10) v.push_back(y);
    for (int i=v.size()-1;i>=0;--i){
        int t=0;
        while (x>=(v[i]<<2))x-=v[i]<<2,t+=4;
        while (x>=(v[i]<<1))x-=v[i]<<1,t+=2;
        while (x>=v[i])x-=v[i],++t;
        printf("%d",t);
    }
    printf("\n");
}
int n, m, q;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Bint a, b;
    read(a); read(b);
    print(a + b);
    return 0;
}

Details

  File "answer.code", line 22
    ull AF = -1ull;
              ^
SyntaxError: invalid decimal literal