oj.uz

답안 #493433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493433 2021-12-11T10:39:40 Z Ronin13 "The Lyuboyn" code (IZhO19_lyuboyn) C++14
19 / 100
 62 ms 6800 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))-1;
    for(int i=0;i<vec[k-2].size();i++){
        if(i&1){
            cur.pb(3*(y+1)+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+1+vec[k-2][i]^y);
        }
        else cur.pb(2*(y+1)+vec[k-2][i]^y);
    }
    x=cur.size();
    for(int i=0;i<x;i++){
        int j=cur[i]/(y+1);
        j=3*(y+1);
        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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<vec[k-2].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
lyuboyn.cpp:60:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |             cur.pb(y+1+vec[k-2][i]^y);
lyuboyn.cpp:62:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   62 |         else cur.pb(2*(y+1)+vec[k-2][i]^y);
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Ok

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Ok

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 312 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 204 KB Ok
7 Correct 1 ms 204 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 6384 KB Ok
2 Correct 27 ms 3268 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 1 ms 312 KB Ok
5 Correct 1 ms 204 KB Ok

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Fail, not exactly k bits are different: line = 31
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 6800 KB Fail, not exactly k bits are different: line = 4095
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 6384 KB Ok
2 Correct 27 ms 3268 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 1 ms 312 KB Ok
5 Correct 1 ms 204 KB Ok
6 Incorrect 1 ms 204 KB Fail, not exactly k bits are different: line = 31
7 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 3452 KB Fail, not exactly k bits are different: line = 7
2 Halted 0 ms 0 KB -