oj.uz

Submission #343153

# Submission time Handle Problem Language Result Execution time Memory
343153 2021-01-03T12:52:29 Z dxz05 "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 915 ms 27932 KB 
//#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

typedef long long ll;
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 4e4;
const int M = 4500;
const int L = 19;

int n, k, t, s;
bool flag[N];

vector<int> ans;
vector<int> good;

bool used[N];

void dfs(int v){
    if (ans.size() == (1 << n)) return;
    used[v] = true;
    ans.push_back(v);
    int cnt = 0;
    for (int x : good){
        if (ans.size() == (1 << n)) return;
        int u = x ^ v;
        if (!used[u]) dfs(u), cnt++;
    }

    if (cnt == 0 && (ans.size() != (1 << n) || !flag[s ^ v])){
        cout << -1;
        exit(0);
    }

}

bool check(vector<int> &v){
    if (ans.size() != (1 << n)) return false;

    for (int i = 1; i < v.size(); i++){
        if (!flag[v[i - 1] ^ v[i]]) return false;
    }
    return (t == 0 || flag[v[0] ^ v.back()]);
}

void solve(int TC) {
    string S;
    cin >> n >> k >> t >> S;
    s = 0;
    for (int i = 0; i < n; i++){
        s *= 2;
        if (S[i] == '1') s++;
    }

    for (int mask = 0; mask < (1 << n); mask++){
        if (__builtin_popcount(mask) == k) good.push_back(mask), flag[mask] = true;
    }

    dfs(s);

    if (check(ans)){
        cout << ans.size() << endl;
        for (int x : ans){
            for (int i = n - 1; i >= 0; i--){
                cout << ((x & (1 << i)) > 0);
            }
            cout << endl;
        }
    } else cout << -1;

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << getCurrentTime() * 1000 << " ms" << endl;

    return 0;
}

Compilation message

lyuboyn.cpp: In function 'void dfs(int)':
lyuboyn.cpp:48:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     if (ans.size() == (1 << n)) return;
      |         ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:53:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if (ans.size() == (1 << n)) return;
      |             ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:58:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     if (cnt == 0 && (ans.size() != (1 << n) || !flag[s ^ v])){
      |                      ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp: In function 'bool check(std::vector<int>&)':
lyuboyn.cpp:66:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if (ans.size() != (1 << n)) return false;
      |         ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 1; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:18:20: warning: statement has no effect [-Wunused-value]
   18 | #define debug(...) 42
      |                    ^~
lyuboyn.cpp:116:9: note: in expansion of macro 'debug'
  116 |         debug(test);
      |         ^~~~~

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 1 ms 364 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Ok
2 Correct 9 ms 11628 KB Ok
3 Correct 5 ms 6248 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 1 ms 748 KB Ok
8 Correct 5 ms 6156 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 27496 KB Ok
2 Correct 438 ms 14060 KB Ok
3 Correct 3 ms 492 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 1 ms 364 KB Ok
2 Correct 26 ms 1228 KB Ok
3 Correct 422 ms 13932 KB Ok
4 Correct 215 ms 7152 KB Ok
5 Correct 2 ms 364 KB Ok
6 Correct 6 ms 492 KB Ok
7 Correct 101 ms 3820 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 27616 KB Ok
2 Correct 915 ms 27872 KB Ok
3 Correct 860 ms 27624 KB Ok
4 Correct 422 ms 14088 KB Ok
5 Correct 425 ms 13804 KB Ok
6 Correct 209 ms 7180 KB Ok
7 Correct 215 ms 7024 KB Ok
8 Correct 104 ms 3900 KB Ok
9 Correct 100 ms 3820 KB Ok
10 Correct 51 ms 2028 KB Ok
11 Correct 4 ms 492 KB Ok
12 Correct 4 ms 492 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 27496 KB Ok
2 Correct 438 ms 14060 KB Ok
3 Correct 3 ms 492 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 26 ms 1228 KB Ok
8 Correct 422 ms 13932 KB Ok
9 Correct 215 ms 7152 KB Ok
10 Correct 2 ms 364 KB Ok
11 Correct 6 ms 492 KB Ok
12 Correct 101 ms 3820 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 864 ms 27616 KB Ok
15 Correct 915 ms 27872 KB Ok
16 Correct 860 ms 27624 KB Ok
17 Correct 422 ms 14088 KB Ok
18 Correct 425 ms 13804 KB Ok
19 Correct 209 ms 7180 KB Ok
20 Correct 215 ms 7024 KB Ok
21 Correct 104 ms 3900 KB Ok
22 Correct 100 ms 3820 KB Ok
23 Correct 51 ms 2028 KB Ok
24 Correct 4 ms 492 KB Ok
25 Correct 4 ms 492 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 877 ms 27368 KB Ok
28 Correct 430 ms 13944 KB Ok
29 Correct 866 ms 27872 KB Ok
30 Correct 55 ms 2028 KB Ok
31 Correct 4 ms 492 KB Ok
32 Correct 25 ms 1132 KB Ok
33 Correct 99 ms 3820 KB Ok
34 Correct 1 ms 492 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 2 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 437 ms 14060 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 13804 KB Ok
2 Correct 867 ms 27368 KB Ok
3 Correct 857 ms 27932 KB Ok
4 Correct 50 ms 2028 KB Ok
5 Correct 2 ms 364 KB Ok
6 Correct 105 ms 3820 KB Ok
7 Correct 863 ms 27616 KB Ok
8 Correct 3 ms 492 KB Ok
9 Correct 1 ms 404 KB Ok
10 Correct 3 ms 492 KB Ok
11 Correct 207 ms 7024 KB Ok
12 Correct 422 ms 13944 KB Ok