Submission #229369

#	Time	Username	Problem	Language	Result	Execution time	Memory
229369		VEGAnn	Popcount (COCI19_popcount)	C++14	110 / 110	6 ms	640 KiB

popcount

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 510;
vector<int> pows[N], fi, se;
int n, k;

void sum(vector<int> &a, vector<int> b){
    for (int i = 0, ost = 0; i < max(sz(a), sz(b)) || ost; i++){
        if (i == sz(a)) a.PB(0);

        int csum = ost + a[i] + (i < sz(b) ? b[i] : 0);

        ost = bool(csum > 9);

        if (csum > 9) csum -= 10;

        a[i] = csum;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    pows[0].clear();
    pows[0].PB(1);

    for (int i = 1; i < n; i++) {
        pows[i] = pows[i - 1];
        sum(pows[i], pows[i - 1]);
    }

    int kol = 0, ln = 2;

    while (1){
        kol++;
        if (ln >= n) break;
        ln += ln;
    }

    cout << kol << '\n';

    for (int len = 2; ; len += len){
        cout << "A=((A&";

        fi.clear();
        se.clear();

        fi.PB(0);
        se.PB(0);

        int half_len = (len >> 1);

        for (int i = 0; i < n; i++)
            if (i % len < half_len)
                sum(fi, pows[i]);
            else sum(se, pows[i]);

        for (int it = sz(fi) - 1; it >= 0; it--)
            cout << fi[it];

        cout << ")+((A&";

        for (int it = sz(se) - 1; it >= 0; it--)
            cout << se[it];

        cout << ")>>" << half_len << "))\n";

        if (len >= n) break;
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45