oj.uz

Submission #222532

# Submission time Handle Problem Language Result Execution time Memory
222532 2020-04-13T08:57:16 Z dwsc Popcount (COCI19_popcount) C++14
110 / 110
 18 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
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;
    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;

    }
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 256 KB Accepted.

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Accepted.
2 Correct 4 ms 256 KB Accepted.
3 Correct 5 ms 256 KB Accepted.
4 Correct 5 ms 384 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 256 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 384 KB Accepted.
15 Correct 5 ms 256 KB Accepted.
16 Correct 5 ms 384 KB Accepted.
17 Correct 5 ms 256 KB Accepted.
18 Correct 6 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
45.0 / 45.0

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