oj.uz

Submission #222436

# Submission time Handle Problem Language Result Execution time Memory
222436 2020-04-13T07:14:30 Z tqbfjotld Popcount (COCI19_popcount) C++14
110 / 110
 6 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

int n,k;

string toStr(int t){

    if (n<64) t%=(1LL<<n);
    if (t==0) return "0";
    string base = "";
    while (t>0){
        base = ((char)('0'+t%10))+base;
        t/=10;
    }
    return base;
}

string genNum(long long interval, bool b){
    if (interval<64){
        unsigned long long t = 0;
        for (int x = 0; x<64; x++){
            if ((x/interval)%2==b){
                t += (1LL<<x);
            }
        }
        if (n<64){
            t%=(1LL<<n);
        }
        string base = "";
        if (t==0) base = "0";
        while (t>0){
            base = (char)('0'+t%10)+base;
            t/=10;
        }
        string res = base;
        int shift = 64;
        while (shift<=n){
            res = "("+res+"+("+base+"<<"+toStr(shift)+"))";
            shift += 64;
        }
        return res;
    }
    else{
        unsigned long long t = -1;
        if (n<64){
            t%=(1LL<<n);
        }
        string base = "";
        if (t==0) base = "0";
        while (t>0){
            base = (char)('0'+t%10)+base;
            t/=10;
        }
        string ans = b?"0":base;
        for (int shift = 1; shift*64<n; shift++){
            if (((shift)/(interval/64))%2==b){
                ans = "("+ans+"+("+base+"<<"+toStr(shift*64)+"))";
            }
        }
        return ans;
    }
}

int main(){
    //printf("%lld\n",1LL<<40);
    scanf("%d%d",&n,&k);
    if (k>10){
        k = 10;
    }
    vector<string> ans;
    for (int x = 0; x<k; x++){
        ans.push_back("A=(((A&"+genNum(1LL<<x,true)+")>>"+toStr(1<<x)+")+(A&"+genNum(1LL<<x,false)+"))");
    }
    printf("%d\n",ans.size());
    for (auto x : ans){
        if (x.size()>1000){
            printf("DIE\n");
        }
        printf("%s\n",x.c_str());
    }
}

Compilation message

popcount.cpp: In function 'int main()':
popcount.cpp:74:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",ans.size());
                   ~~~~~~~~~~^
popcount.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~

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 5 ms 256 KB Accepted.
4 Correct 4 ms 256 KB Accepted.
5 Correct 5 ms 256 KB Accepted.
6 Correct 5 ms 256 KB Accepted.
7 Correct 4 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 384 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 256 KB Accepted.

Subtask #3
35.0 / 35.0

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