답안 #861118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861118 2023-10-15T11:08:10 Z Alfraganus "The Lyuboyn" code (IZhO19_lyuboyn) C++14
52 / 100
1000 ms 43504 KB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fs first
#define ss second
#define str string
#define all(a) a.begin(), a.end()
#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;
#define each(x, a) for (auto x : a)

vector<int> ans;
vector<bool> used;
int n, k, t, sx = 0;

bool good(int s1, int s2){
    int ans = 0;
    while(s1 > 0 or s2 > 0){
        ans += (s1 % 2 != s2 % 2);
        s1 /= 2;
        s2 /= 2;
    }
    return ans == k;
}

bool dfs(int node, int step){
    if(step == (1 << n) - 1){
        if(t == 0){
            ans.push_back(node);
            return true;
        }
        if(good(sx, node))
            ans.push_back(node);
        else
            return false;
        return true;
    }
    used[node] = 1;
    if(k == 1 or k == 17){
        for (int i = 0; i < n; i++)
        {
            if (k == 1 and !used[node ^ (1 << i)] and dfs(node ^ (1 << i), step + 1))
            {
                ans.push_back(node);
                return true;
            }
            else if (k == 17 and !used[node ^ (node ^ (1 << i))] and dfs(node ^ (node ^ (1 << i)), step + 1))
            {
                ans.push_back(node);
                return true;
            }
        }
    }
    else if(k == 2 or k == 16){
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (k == 2 and !used[(node ^ (1 << i)) ^ (1 << j)] and dfs((node ^ (1 << i)) ^ (1 << j), step + 1))
                {
                    ans.push_back(node);
                    return true;
                }
                else if (k == 16 and !used[node ^ ((node ^ (1 << i)) ^ (1 << j))] and dfs(node ^ ((node ^ (1 << i)) ^ (1 << j)), step + 1)){
                    ans.push_back(node);
                    return true;
                }
            }
        }
    }
    else if(k == 3 or k == 15){
        for(int i = 0; i < n; i ++){
            for(int j = i + 1; j < n; j ++){
                for(int x = j + 1; x < n; x ++){
                    if (k == 3 and !used[((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)] and dfs(((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x), step + 1))
                    {
                        ans.push_back(node);
                        return true;
                    }
                    else if (k == 15 and !used[(node ^ ((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x))] and dfs(node ^ (((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)), step + 1)){
                        ans.push_back(node);
                        return true;
                    }
                }
            }
        }
    }
    else if (k == 4 or k == 14)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for(int i1 = x + 1; i1 < n; i1 ++){
                        if (k == 4 and !used[(((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)] and dfs((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1), step + 1))
                        {
                            ans.push_back(node);
                            return true;
                        }
                        else if (k == 14 and !used[node ^ ((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1))] and dfs(node ^ ((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)), step + 1))
                        {
                            ans.push_back(node);
                            return true;
                        }
                    }
                }
            }
        }
    }
    else if(k == 5 or k == 13){
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        for(int i2 = i1 + 1; i2 < n; i2 ++){
                            if (k == 5 and !used[((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)] and dfs(((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2), step + 1))
                            {
                                ans.push_back(node);
                                return true;
                            }
                            else if (k == 13 and !used[node ^ (((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2))] and dfs(node ^ (((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)), step + 1))
                            {
                                ans.push_back(node);
                                return true;
                            }
                        }
                    }
                }
            }
        }
    }
    else if (k == 6 or k == 12)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            for(int i3 = i2 + 1; i3 < n; i3 ++){
                                if (k == 12 and !used[node ^ ((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3))] and dfs(node ^ ((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)), step + 1))
                                {
                                    ans.push_back(node);
                                    return true;
                                }
                                else if (k == 6 and !used[((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3))] and dfs(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)), step + 1)){
                                    ans.push_back(node);
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    else if(k == 7 or k == 11){
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                for(int i4 = i3 + 1; i4 < n; i4 ++){
                                    if (k == 7 and !used[((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)] and dfs(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4), step + 1))
                                    {
                                        ans.push_back(node);
                                        return true;
                                    }
                                    else if (k == 11 and !used[node ^ (((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4))] and dfs(node ^ (((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)), step + 1)){
                                        ans.push_back(node);
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    else if (k == 8 or k == 10)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                for (int i4 = i3 + 1; i4 < n; i4++)
                                {
                                    for(int i5 = i4 + 1; i5 < n; i5 ++){
                                        if (k == 8 and !used[(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)] and dfs((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5), step + 1))
                                        {
                                            ans.push_back(node);
                                            return true;
                                        }
                                        else if (k == 10 and !used[node ^ ((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5))] and dfs(node ^ ((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)), step + 1)){
                                            ans.push_back(node);
                                            return true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    else if(k == 9){
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int x = j + 1; x < n; x++)
                {
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                for (int i4 = i3 + 1; i4 < n; i4++)
                                {
                                    for (int i5 = i4 + 1; i5 < n; i5++)
                                    {
                                        for(int i6 = i5 + 1; i6 < n; i6 ++){
                                            if (!used[((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)) ^ (1 << i6)] and dfs(((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)) ^ (1 << i6), step + 1))
                                            {
                                                ans.push_back(node);
                                                return true;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    used[node] = 0;
    return false;
}

void solve(){
    cin >> n >> k >> t;
    str s;
    cin >> s;
    for(int i = s.size() - 1; i >= 0; i --){
        if(s[i] == '1'){
            sx += (1 << (s.size() - 1 - i));
        }
    }
    if(k % 2 == 0){
        cout << -1;
        return;
    }
    used.resize((1 << n));
    if(dfs(sx, 0)){
        cout << (1 << n) << endl;
        reverse(all(ans));
        for(int i = 0; i < ans.size(); i ++){
            str s = "";
            for(int j = 0; j < n; j ++){
                if(ans[i] % 2 == 0)
                    s += '0';
                else
                    s += '1';
                ans[i] >>= 1;
            }
            reverse(all(s));
            cout << s << endl;
        }
    }
    else{
        cout << -1;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Compilation message

lyuboyn.cpp: In function 'void solve()':
lyuboyn.cpp:290:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |         for(int i = 0; i < ans.size(); i ++){
      |                        ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 344 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 43468 KB Ok
2 Correct 38 ms 21716 KB Ok
3 Correct 1 ms 600 KB Ok
4 Correct 0 ms 344 KB Ok
5 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 2 ms 1628 KB Ok
3 Correct 39 ms 21828 KB Ok
4 Correct 19 ms 11004 KB Ok
5 Correct 1 ms 344 KB Ok
6 Correct 1 ms 856 KB Ok
7 Correct 8 ms 5816 KB Ok
8 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 43360 KB Ok
2 Correct 78 ms 43504 KB Ok
3 Correct 72 ms 43464 KB Ok
4 Correct 38 ms 21856 KB Ok
5 Correct 37 ms 21712 KB Ok
6 Correct 19 ms 10976 KB Ok
7 Correct 20 ms 10976 KB Ok
8 Correct 8 ms 5720 KB Ok
9 Correct 8 ms 5720 KB Ok
10 Correct 4 ms 2904 KB Ok
11 Correct 1 ms 604 KB Ok
12 Correct 1 ms 604 KB Ok
13 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 43468 KB Ok
2 Correct 38 ms 21716 KB Ok
3 Correct 1 ms 600 KB Ok
4 Correct 0 ms 344 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 344 KB Ok
7 Correct 2 ms 1628 KB Ok
8 Correct 39 ms 21828 KB Ok
9 Correct 19 ms 11004 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 856 KB Ok
12 Correct 8 ms 5816 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 81 ms 43360 KB Ok
15 Correct 78 ms 43504 KB Ok
16 Correct 72 ms 43464 KB Ok
17 Correct 38 ms 21856 KB Ok
18 Correct 37 ms 21712 KB Ok
19 Correct 19 ms 10976 KB Ok
20 Correct 20 ms 10976 KB Ok
21 Correct 8 ms 5720 KB Ok
22 Correct 8 ms 5720 KB Ok
23 Correct 4 ms 2904 KB Ok
24 Correct 1 ms 604 KB Ok
25 Correct 1 ms 604 KB Ok
26 Correct 0 ms 348 KB Ok
27 Execution timed out 1064 ms 348 KB Time limit exceeded
28 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1049 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -