oj.uz

Submission #493437

# Submission time Handle Problem Language Result Execution time Memory
493437 2021-12-11T10:45:25 Z Ronin13 "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 57 ms 6880 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 0 ms 204 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6472 KB Ok
2 Correct 28 ms 3256 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 2 ms 460 KB Ok
3 Correct 29 ms 3364 KB Ok
4 Correct 14 ms 1864 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 5 ms 1100 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6840 KB Ok
2 Correct 56 ms 6776 KB Ok
3 Correct 56 ms 6720 KB Ok
4 Correct 27 ms 3416 KB Ok
5 Correct 27 ms 3364 KB Ok
6 Correct 13 ms 1864 KB Ok
7 Correct 14 ms 1744 KB Ok
8 Correct 5 ms 1100 KB Ok
9 Correct 5 ms 1100 KB Ok
10 Correct 3 ms 588 KB Ok
11 Correct 1 ms 316 KB Ok
12 Correct 0 ms 332 KB Ok
13 Correct 1 ms 204 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6472 KB Ok
2 Correct 28 ms 3256 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 2 ms 460 KB Ok
8 Correct 29 ms 3364 KB Ok
9 Correct 14 ms 1864 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 5 ms 1100 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 55 ms 6840 KB Ok
15 Correct 56 ms 6776 KB Ok
16 Correct 56 ms 6720 KB Ok
17 Correct 27 ms 3416 KB Ok
18 Correct 27 ms 3364 KB Ok
19 Correct 13 ms 1864 KB Ok
20 Correct 14 ms 1744 KB Ok
21 Correct 5 ms 1100 KB Ok
22 Correct 5 ms 1100 KB Ok
23 Correct 3 ms 588 KB Ok
24 Correct 1 ms 316 KB Ok
25 Correct 0 ms 332 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 56 ms 6832 KB Ok
28 Correct 27 ms 3396 KB Ok
29 Correct 57 ms 6796 KB Ok
30 Correct 3 ms 696 KB Ok
31 Correct 0 ms 312 KB Ok
32 Correct 2 ms 460 KB Ok
33 Correct 6 ms 1100 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 0 ms 204 KB Ok
36 Correct 0 ms 332 KB Ok
37 Correct 0 ms 204 KB Ok
38 Correct 28 ms 3524 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3396 KB Ok
2 Correct 56 ms 6828 KB Ok
3 Correct 54 ms 6880 KB Ok
4 Correct 3 ms 588 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 5 ms 1100 KB Ok
7 Correct 54 ms 6828 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 0 ms 204 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 13 ms 1864 KB Ok
12 Correct 26 ms 3456 KB Ok