답안 #861124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861124 2023-10-15T11:21:26 Z Alfraganus "The Lyuboyn" code (IZhO19_lyuboyn) C++14
52 / 100
1000 ms 39364 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){
        int x = node;
        for (int i = 0; i < n; i++)
        {
            x ^= (1 << i);
            if (k == 1 and !used[x] and dfs(x, step + 1))
            {
                ans.push_back(node);
                return true;
            }
            else if (k == 17 and !used[node ^ x] and dfs(node ^ x, step + 1))
            {
                ans.push_back(node);
                return true;
            }
            x ^= (1 << i);
        }
    }
    else if(k == 2 or k == 16){
        int x = node;
        for (int i = 0; i < n; i++)
        {
            x ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                x ^= (1 << j);
                if (k == 2 and !used[x] and dfs(x, step + 1))
                {
                    ans.push_back(node);
                    return true;
                }
                else if (k == 16 and !used[node ^ x] and dfs(node ^ x, step + 1)){
                    ans.push_back(node);
                    return true;
                }
                x ^= (1 << j);
            }
            x ^= (1 << i);
        }
    }
    else if(k == 3 or k == 15){
        int y = node;
        for(int i = 0; i < n; i ++){
            y ^= (1 << i);
            for(int j = i + 1; j < n; j ++){
                y ^= (1 << j);
                for(int x = j + 1; x < n; x ++){
                    y ^= (1 << x);
                    if (k == 3 and !used[y] and dfs(y, step + 1))
                    {
                        ans.push_back(node);
                        return true;
                    }
                    else if (k == 15 and !used[node ^ y] and dfs(node ^ y, step + 1)){
                        ans.push_back(node);
                        return true;
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if (k == 4 or k == 14)
    {
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for(int i1 = x + 1; i1 < n; i1 ++){
                        y ^= (1 << i1);
                        if (k == 4 and !used[y] and dfs(y, step + 1))
                        {
                            ans.push_back(node);
                            return true;
                        }
                        else if (k == 14 and !used[node ^ y] and dfs(node ^ y, step + 1))
                        {
                            ans.push_back(node);
                            return true;
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if(k == 5 or k == 13){
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        y ^= (1 << i1);
                        for(int i2 = i1 + 1; i2 < n; i2 ++){
                            y ^= (1 << 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;
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if (k == 6 or k == 12)
    {
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        y ^= (1 << i1);
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            y ^= (1 << i2);
                            for(int i3 = i2 + 1; i3 < n; i3 ++){
                                y ^= (1 << i3);
                                if (k == 12 and !used[node ^ y] and dfs(node ^ y, step + 1))
                                {
                                    ans.push_back(node);
                                    return true;
                                }
                                else if (k == 6 and !used[y] and dfs(y, step + 1)){
                                    ans.push_back(node);
                                    return true;
                                }
                                y ^= (1 << i3);
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if(k == 7 or k == 11){
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        y ^= (1 << i1);
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            y ^= (1 << i2);
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                y ^= (1 << i3);
                                for(int i4 = i3 + 1; i4 < n; i4 ++){
                                    y ^= (1 << i4);
                                    if (k == 7 and !used[y] and dfs(y, step + 1))
                                    {
                                        ans.push_back(node);
                                        return true;
                                    }
                                    else if (k == 11 and !used[node ^ y] and dfs(node ^ y, step + 1)){
                                        ans.push_back(node);
                                        return true;
                                    }
                                    y ^= (1 << i4);
                                }
                                y ^= (1 << i3);
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if (k == 8 or k == 10)
    {
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        y ^= (1 << i1);
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            y ^= (1 << i2);
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                y ^= (1 << i3);
                                for (int i4 = i3 + 1; i4 < n; i4++)
                                {
                                    y ^= (1 << i4);
                                    for(int i5 = i4 + 1; i5 < n; i5 ++){
                                        y ^= (1 << i5);
                                        if (k == 8 and !used[y] and dfs(y, step + 1))
                                        {
                                            ans.push_back(node);
                                            return true;
                                        }
                                        else if (k == 10 and !used[node ^ y] and dfs(node ^ y, step + 1)){
                                            ans.push_back(node);
                                            return true;
                                        }
                                    }
                                    y ^= (1 << i4);
                                }
                                y ^= (1 << i3);
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if(k == 9){
        int y = node;
        for (int i = 0; i < n; i++)
        {
            y ^= (1 << i);
            for (int j = i + 1; j < n; j++)
            {
                y ^= (1 << j);
                for (int x = j + 1; x < n; x++)
                {
                    y ^= (1 << x);
                    for (int i1 = x + 1; i1 < n; i1++)
                    {
                        y ^= (1 << i1);
                        for (int i2 = i1 + 1; i2 < n; i2++)
                        {
                            y ^= (1 << i2);
                            for (int i3 = i2 + 1; i3 < n; i3++)
                            {
                                y ^= (1 << i3);
                                for (int i4 = i3 + 1; i4 < n; i4++)
                                {
                                    y ^= (1 << i4);
                                    for (int i5 = i4 + 1; i5 < n; i5++)
                                    {
                                        y ^= (1 << i5);
                                        for(int i6 = i5 + 1; i6 < n; i6 ++){
                                            y ^= (1 << i6);
                                            if (!used[y] and dfs(y, step + 1))
                                            {
                                                ans.push_back(node);
                                                return true;
                                            }
                                            y ^= (1 << i6);
                                        }
                                        y ^= (1 << i5);
                                    }
                                    y ^= (1 << i4);
                                }
                                y ^= (1 << i3);
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    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:388:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  388 |         for(int i = 0; i < ans.size(); i ++){
      |                        ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 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 0 ms 348 KB Ok
8 Correct 0 ms 456 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 39316 KB Ok
2 Correct 35 ms 19676 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 2 ms 1628 KB Ok
3 Correct 35 ms 19668 KB Ok
4 Correct 17 ms 9952 KB Ok
5 Correct 1 ms 344 KB Ok
6 Correct 1 ms 604 KB Ok
7 Correct 8 ms 5260 KB Ok
8 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 39364 KB Ok
2 Correct 79 ms 39336 KB Ok
3 Correct 75 ms 39364 KB Ok
4 Correct 38 ms 19652 KB Ok
5 Correct 38 ms 19676 KB Ok
6 Correct 18 ms 10048 KB Ok
7 Correct 17 ms 9952 KB Ok
8 Correct 8 ms 5212 KB Ok
9 Correct 8 ms 5212 KB Ok
10 Correct 5 ms 2648 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 0 ms 460 KB Ok
13 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 39316 KB Ok
2 Correct 35 ms 19676 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 2 ms 1628 KB Ok
8 Correct 35 ms 19668 KB Ok
9 Correct 17 ms 9952 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 604 KB Ok
12 Correct 8 ms 5260 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 78 ms 39364 KB Ok
15 Correct 79 ms 39336 KB Ok
16 Correct 75 ms 39364 KB Ok
17 Correct 38 ms 19652 KB Ok
18 Correct 38 ms 19676 KB Ok
19 Correct 18 ms 10048 KB Ok
20 Correct 17 ms 9952 KB Ok
21 Correct 8 ms 5212 KB Ok
22 Correct 8 ms 5212 KB Ok
23 Correct 5 ms 2648 KB Ok
24 Correct 1 ms 348 KB Ok
25 Correct 0 ms 460 KB Ok
26 Correct 0 ms 348 KB Ok
27 Execution timed out 1020 ms 348 KB Time limit exceeded
28 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1038 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -