oj.uz

Submission #222457

# Submission time Handle Problem Language Result Execution time Memory
222457 2020-04-13T07:42:33 Z dwsc Popcount (COCI19_popcount) C++14
65 / 110
 6 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
string checkbit(int i){
    return "((A&(1<<"+to_string(i)+"))>>"+to_string(i)+")";
}
string bitshift(int i){
    return "(1<<"+to_string(i)+")";
}
string getmaxint(int n){
    return "((1<<"+to_string(n)+")-1)";
}
int f1(int a,int i){
    return ((a&(1<<i))>>i);
}
int f2(int i){
    return (1<<i);
}
int f3(int i){
    return ((1<<i)-1);
}
int main(){
    int n,k;
    cin >> n >> k;
    if (k*4 >= n){
        cout << (n+3)/4 << "\n";
        for (int i = 0; i < n; i+= 4){
            string add = checkbit(i),sub="("+getmaxint(n)+"-"+bitshift(i)+")";
            for (int j = i+1; j < min(i+4,n); j++){
                add = "("+add+"+"+checkbit(j)+")";
                sub = "("+sub+"-"+bitshift(j)+")";
            }
            sub = "(A&"+sub+")";
            string finalString = "A=("+add+"+"+sub+")";
            cout << finalString << "\n";
        }
    }
    else{
        //for (int a = 4; a < (1<<n); a++){
        int numboxes = n,boxsize = 1;
        //int temp = a;
        //cout << temp << "hi\n";
        int val = 0,tempn = n;
        while (tempn  != 1){
            val++;
            tempn = (tempn+1)/2;
        }
        cout << val << "\n";
        while (numboxes != 1){
            string bigbox = "0",smallbox = "0";
            int addto = 0;
            int num = 0;
            //int bigval = 0,smallval = 0;
            for (int i = 0; i < n; i++){
                num++;
                if (num > boxsize){
                    num-=boxsize;
                    addto = 1-addto;
                }
                if (addto){
                    //bigval += f2(i);
                    bigbox = "("+bigbox+"+"+bitshift(i)+")";
                }
                else{
                    //smallval += f2(i);
                    smallbox = "("+smallbox+"+"+bitshift(i)+")";
                }
            }
            string finalstring = "A=(((A&"+bigbox+")>>"+to_string(boxsize)+")+(A&"+smallbox+"))";
            assert(finalstring.length() <= 1000);
            cout << finalstring << "\n";
            //temp = ((temp&bigval)>>boxsize)+(temp&smallval);
            numboxes = (numboxes+1)/2;
            boxsize *= 2;

        }
        //if (temp != __builtin_popcount(a)) cout << "hi\n";
        //}
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 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 4 ms 256 KB Accepted.
4 Correct 5 ms 256 KB Accepted.
5 Correct 5 ms 256 KB Accepted.
6 Correct 5 ms 256 KB Accepted.
7 Correct 5 ms 256 KB Accepted.
8 Correct 5 ms 256 KB Accepted.
9 Correct 5 ms 384 KB Accepted.
10 Correct 5 ms 256 KB Accepted.
11 Correct 5 ms 256 KB Accepted.
12 Correct 5 ms 256 KB Accepted.
13 Correct 5 ms 256 KB Accepted.
14 Correct 5 ms 256 KB Accepted.
15 Correct 5 ms 256 KB Accepted.
16 Correct 4 ms 256 KB Accepted.
17 Correct 6 ms 256 KB Accepted.
18 Correct 5 ms 256 KB Accepted.
19 Correct 5 ms 256 KB Accepted.
20 Correct 5 ms 256 KB Accepted.
21 Correct 5 ms 256 KB Accepted.

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -