Submission #493437

#	Time	Username	Problem	Language	Result	Execution time	Memory
493437		Ronin13	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	100 / 100	57 ms	6880 KiB

lyuboyn

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

int conv(string s){
    int x=0;
    int msb=s.size()-1;
    for(int i=0;i<s.size();i++){
        int bt=s[i]-'0';
        x+=bt*(1<<(msb--));
    }
    return x;
}

string revconv(int a,int n){
    string s="";
    int len=log2(a);
    while(s.size()<n){
        int x=a&1;
        char c=x+'0';
        s+=c;
        a>>=1;
    }
    reverse(s.begin(),s.end());
    return s;
}

vector<int>easy(int n){
    vector<int>vec;
    vec.pb(0);
    for(int i=1;i<=n;i++){
        for(int j=vec.size()-1;j>=0;j--)vec.pb(vec[j]+(1<<(i-1)));
    }
    return vec;
}

vector<vector<int> >vec(20);

vector<int>hard(int k,int n){
    vector<int>cur;
    int y=(1<<(n-2));
    int z=(1<<(k-1))-1;
    for(int i=0;i<vec[k-2].size();i++){
        if(i&1){
            cur.pb(3*y+vec[k-2][i]);
        }
        else cur.pb(vec[k-2][i]);
    }
    int x=cur.size();
    for(int i=x-1;i>=0;i--){
        if(i&1){
            cur.pb(y+vec[k-2][i]^z);
        }
        else cur.pb(2*y+vec[k-2][i]^z);
    }
    x=cur.size();
    for(int i=0;i<x;i++){
        int j=3*y;
        cur.pb(cur[i]^j);
    }
    return cur;
}

void solve(){
    int n,k,t;cin>>n>>k>>t;
    string s;cin>>s;
    int st=conv(s);
    if(k%2==0){
        cout<<-1;

        return;
    }
    int n1=n,k1=k;
    while(k1!=1){
        n1-=2;
        k1-=2;
    }
    vec[1]=easy(n1);
    n1+=2;
    for(int i=3;i<=k;i+=2){
        vec[i]=hard(i,n1);n1+=2;
    }
    cout<<vec[k].size()<<"\n";
    for(int to:vec[k]){
        cout<<revconv(to^st,n)<<"\n";
    }
}


main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int test=1;//cin>>test;
    while(test--)solve();
}

Compilation message (stderr)

lyuboyn.cpp: In function 'int conv(std::string)':
lyuboyn.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
lyuboyn.cpp: In function 'std::string revconv(int, int)':
lyuboyn.cpp:27:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while(s.size()<n){
      |                   ^
lyuboyn.cpp:26:9: warning: unused variable 'len' [-Wunused-variable]
   26 |     int len=log2(a);
      |         ^~~
lyuboyn.cpp: In function 'std::vector<int> hard(int, int)':
lyuboyn.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<vec[k-2].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
lyuboyn.cpp:61:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   61 |             cur.pb(y+vec[k-2][i]^z);
lyuboyn.cpp:63:24: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   63 |         else cur.pb(2*y+vec[k-2][i]^z);
lyuboyn.cpp: At global scope:
lyuboyn.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main(){
      | ^~~~

• Subtask 1: 0 / 0
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 31 / 31
• Subtask 8: 17 / 17