oj.uz

Submission #229369

# Submission time Handle Problem Language Result Execution time Memory
229369 2020-05-04T10:34:03 Z VEGAnn Popcount (COCI19_popcount) C++14
110 / 110
 6 ms 640 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Accepted.
2 Correct 5 ms 384 KB Accepted.
3 Correct 4 ms 384 KB Accepted.
4 Correct 4 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 5 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 384 KB Accepted.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Accepted.

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Accepted.
2 Correct 4 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 4 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 384 KB Accepted.
12 Correct 5 ms 384 KB Accepted.
13 Correct 5 ms 384 KB Accepted.
14 Correct 5 ms 384 KB Accepted.
15 Correct 5 ms 384 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 360 KB Accepted.

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Accepted.
2 Correct 5 ms 512 KB Accepted.
3 Correct 6 ms 512 KB Accepted.
4 Correct 6 ms 640 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 5 ms 384 KB Accepted.
11 Correct 5 ms 384 KB Accepted.
12 Correct 6 ms 512 KB Accepted.