Submission #222567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222567	2020-04-13T11:05:19 Z	lyc	Popcount (COCI19_popcount)	C++14	110 / 110	15 ms	512 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Accepted.
2	Correct	5 ms	512 KB	Accepted.
3	Correct	5 ms	384 KB	Accepted.
4	Correct	4 ms	384 KB	Accepted.
5	Correct	4 ms	384 KB	Accepted.
6	Correct	5 ms	384 KB	Accepted.
7	Correct	5 ms	384 KB	Accepted.
8	Correct	5 ms	384 KB	Accepted.
9	Correct	5 ms	384 KB	Accepted.
10	Correct	5 ms	384 KB	Accepted.
11	Correct	5 ms	256 KB	Accepted.
12	Correct	5 ms	384 KB	Accepted.
13	Correct	5 ms	384 KB	Accepted.
14	Correct	5 ms	384 KB	Accepted.

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	512 KB	Accepted.

Subtask #3

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Accepted.
2	Correct	5 ms	384 KB	Accepted.
3	Correct	5 ms	384 KB	Accepted.
4	Correct	5 ms	384 KB	Accepted.
5	Correct	5 ms	384 KB	Accepted.
6	Correct	5 ms	384 KB	Accepted.
7	Correct	5 ms	384 KB	Accepted.
8	Correct	5 ms	384 KB	Accepted.
9	Correct	5 ms	384 KB	Accepted.
10	Correct	4 ms	384 KB	Accepted.
11	Correct	5 ms	384 KB	Accepted.
12	Correct	5 ms	384 KB	Accepted.
13	Correct	5 ms	384 KB	Accepted.
14	Correct	5 ms	256 KB	Accepted.
15	Correct	5 ms	256 KB	Accepted.
16	Correct	5 ms	384 KB	Accepted.
17	Correct	5 ms	384 KB	Accepted.
18	Correct	5 ms	384 KB	Accepted.
19	Correct	5 ms	384 KB	Accepted.
20	Correct	5 ms	384 KB	Accepted.
21	Correct	5 ms	384 KB	Accepted.

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	384 KB	Accepted.
2	Correct	8 ms	384 KB	Accepted.
3	Correct	12 ms	384 KB	Accepted.
4	Correct	13 ms	384 KB	Accepted.
5	Correct	6 ms	384 KB	Accepted.
6	Correct	6 ms	384 KB	Accepted.
7	Correct	5 ms	384 KB	Accepted.
8	Correct	6 ms	384 KB	Accepted.
9	Correct	7 ms	384 KB	Accepted.
10	Correct	8 ms	384 KB	Accepted.
11	Correct	7 ms	384 KB	Accepted.
12	Correct	14 ms	384 KB	Accepted.