oj.uz

Submission #337105

# Submission time Handle Problem Language Result Execution time Memory
337105 2020-12-18T13:26:51 Z talant117408 "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 139 ms 31180 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

string inverse(string s, int l, int r){
    if(l > r) return s;
    for(int i = l; i <= r; i++){
        s[i] = (s[i] == '0' ? '1' : '0');
    }
    return s;
}

int main(){
    do_not_disturb
    
    int n, k, type;
    string s;
    cin >> n >> k >> type >> s;
    if(k%2 == 0){
        cout << -1;
        return 0;
    }
    
    vector <string> grey;
    grey.pb("0");
    grey.pb("1");
    
    for(int i = 2; i <= k+1; i++){
        vector <string> tmp = grey;
        reverse(all(tmp));
        grey.insert(grey.end(), all(tmp));
        for(int j = 0; j < sz(grey)/2; j++) grey[j] = "0"+grey[j];
        for(int j = sz(grey)/2; j < sz(grey); j++) grey[j] = "1"+grey[j];
    }
    
    for(int i = 1; i < sz(grey); i += 2){
        grey[i] = inverse(grey[i], 0, sz(grey[i])-1);
    }
    
    for(int i = k+2; i <= n; i++){
        vector <string> tmp = grey;
        reverse(all(tmp));
        grey.insert(grey.end(), all(tmp));
        for(int j = 0; j < sz(grey)/2; j++) grey[j] = "0"+grey[j];
        for(int j = sz(grey)/2; j < sz(grey); j++) grey[j] = "1"+grey[j];
        for(int j = sz(grey)/2; j < sz(grey); j++) grey[j] = inverse(grey[j], sz(grey[j])-(k-1), sz(grey[j])-1);
    }
    
    int ind;
    for(int i = 0; i < sz(grey); i ++){
        if(grey[i] == s){
            ind = i;
            break;
        }
    }
    
    cout << binpow(2, n) << endl;
    for(int i = ind; i < sz(grey); i++) cout << grey[i] << endl;
    for(int i = 0; i < ind; i++) cout << grey[i] << endl;
    
    return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:145:9: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |     int ind;
      |         ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 30284 KB Ok
2 Correct 54 ms 15188 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Ok
2 Correct 2 ms 876 KB Ok
3 Correct 56 ms 15188 KB Ok
4 Correct 23 ms 6740 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 492 KB Ok
7 Correct 9 ms 2660 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 30152 KB Ok
2 Correct 127 ms 30308 KB Ok
3 Correct 123 ms 30156 KB Ok
4 Correct 64 ms 15308 KB Ok
5 Correct 57 ms 15188 KB Ok
6 Correct 24 ms 6740 KB Ok
7 Correct 22 ms 6740 KB Ok
8 Correct 9 ms 2532 KB Ok
9 Correct 10 ms 2532 KB Ok
10 Correct 5 ms 1536 KB Ok
11 Correct 1 ms 376 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 30284 KB Ok
2 Correct 54 ms 15188 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 0 ms 364 KB Ok
7 Correct 2 ms 876 KB Ok
8 Correct 56 ms 15188 KB Ok
9 Correct 23 ms 6740 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 492 KB Ok
12 Correct 9 ms 2660 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 132 ms 30152 KB Ok
15 Correct 127 ms 30308 KB Ok
16 Correct 123 ms 30156 KB Ok
17 Correct 64 ms 15308 KB Ok
18 Correct 57 ms 15188 KB Ok
19 Correct 24 ms 6740 KB Ok
20 Correct 22 ms 6740 KB Ok
21 Correct 9 ms 2532 KB Ok
22 Correct 10 ms 2532 KB Ok
23 Correct 5 ms 1536 KB Ok
24 Correct 1 ms 376 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 119 ms 31180 KB Ok
28 Correct 62 ms 15188 KB Ok
29 Correct 139 ms 30284 KB Ok
30 Correct 5 ms 1516 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 3 ms 876 KB Ok
33 Correct 10 ms 2532 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 61 ms 15700 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15700 KB Ok
2 Correct 119 ms 31128 KB Ok
3 Correct 135 ms 30152 KB Ok
4 Correct 5 ms 1516 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 10 ms 2532 KB Ok
7 Correct 126 ms 30156 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 24 ms 6740 KB Ok
12 Correct 64 ms 15188 KB Ok