Submission #222528

#	Time	Username	Problem	Language	Result	Execution time	Memory
222528		dwsc	Popcount (COCI19_popcount)	C++14	110 / 110	19 ms	384 KiB

popcount

#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);
}
string add(string s1,string s2){
    vector<int> v;
    int carry = 0;
    if (s1.length() < s2.length()) swap(s1,s2);
    while (s1.length() > s2.length()) s2 = "0"+s2;
    for (int i = s1.length()-1; i >= 0; i--){
        int v1 = s1[i]-48,v2 = s2[i]-48;
        v.push_back((v1+v2+carry)%10);
        carry = (v1+v2+carry)>=10;
    }
    if (carry) v.push_back(carry);
    string s = "";
    for (int i = v.size()-1; i >= 0; i--) s +=(char)(v[i]+48);
    return s;
}
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{
        int numboxes = n,boxsize = 1;
        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;
            string counter = "1";
            for (int i = 0; i < n; i++){
                num++;
                if (num > boxsize){
                    num-=boxsize;
                    addto = 1-addto;
                }
                if (addto){
                    bigbox = add(bigbox,counter);
                }
                else{
                    smallbox = add(smallbox,counter);
                }
                //cout << bigbox << " " << smallbox << "\n";
                counter = add(counter,counter);
                //cout << counter << "hi\n";
            }
            string finalstring = "A=(((A&"+bigbox+")>>"+to_string(boxsize)+")+(A&"+smallbox+"))";
            assert(finalstring.length() <= 1000);
            cout << finalstring << "\n";
            numboxes = (numboxes+1)/2;
            boxsize *= 2;

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

Compilation message (stderr)

popcount.cpp: In function 'int main()':
popcount.cpp:64:17: warning: unused variable 'bigval' [-Wunused-variable]
             int bigval = 0,smallval = 0;
                 ^~~~~~
popcount.cpp:64:28: warning: unused variable 'smallval' [-Wunused-variable]
             int bigval = 0,smallval = 0;
                            ^~~~~~~~

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