Submission #222567

#	Time	Username	Problem	Language	Result	Execution time	Memory
222567		lyc	Popcount (COCI19_popcount)	C++14	110 / 110	15 ms	512 KiB

popcount

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

string add(string p, string q) {
    if (SZ(p) > SZ(q)) swap(p,q);
    reverse(p.begin(),p.end());
    reverse(q.begin(),q.end());
    string res = "";
    int carry = 0;
    FOR(i,0,SZ(p)-1){
        int cur = (p[i]-'0')+(q[i]-'0')+carry;
        res += '0' + cur%10;
        carry = cur/10;
    }
    FOR(i,SZ(p),SZ(q)-1){
        int cur = (q[i]-'0')+carry;
        res += '0' + cur%10;
        carry = cur/10;
    }
    if (carry) res += '0' + carry;
    reverse(res.begin(),res.end());
    return res;
}

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

    int N, K; cin >> N >> K;

    vector<string> code;
    for (int seg = 1; seg < N; seg <<= 1) {
        string p = "0", q = "0";
        string d = "1";

        int f = 1, cnt = 0;
        FOR(i,0,N-1){
            if (f) p = add(p,d);
            else q = add(q,d);
            if (++cnt == seg) cnt = 0, f = !f;
            d = add(d,d);
        }

        code.push_back("A=((A&" + p + ")+((A&" + q + ")>>" + to_string(seg) + "))");
    }

    cout << SZ(code) << '\n';
    for (auto& s : code){
        cout << s << '\n';
    }
}

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