답안 #861498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861498 2023-10-16T11:17:26 Z Alfraganus "The Lyuboyn" code (IZhO19_lyuboyn) C++14
52 / 100
81 ms 35280 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 == 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 == 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 == 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);
        }
    }
    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 or k == 9)
    {
        cout << -1;
        return;
    }
    used.resize((1 << n));
    bool flag = 2 * k > n;
    if(2 * k > n)
        k = n - k;
    if (dfs(sx, 0))
    {
        cout << (1 << n) << endl;
        if(flag){
            reverse(all(ans));
            for(int i = 0; i < ans.size(); i ++){
                str s = "";
                if((i & 1)){
                    for(int j = 0; j < n; j ++){
                        if(ans[i] % 2 == 0)
                            s += '1';
                        else
                            s += '0';
                        ans[i] /= 2;
                    }
                    cout << s << endl;
                }
                else{
                    for (int j = 0; j < n; j++)
                    {
                        if (ans[i] % 2 == 0)
                            s += '0';
                        else
                            s += '1';
                        ans[i] /= 2;
                    }
                    cout << s << endl;
                }
            }
        }
        else{
            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:213:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |             for(int i = 0; i < ans.size(); i ++){
      |                            ~~^~~~~~~~~~~~
lyuboyn.cpp:240:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |             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 0 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 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 35276 KB Ok
2 Correct 41 ms 17628 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 2 ms 1372 KB Ok
3 Correct 34 ms 17816 KB Ok
4 Correct 20 ms 9148 KB Ok
5 Correct 0 ms 344 KB Ok
6 Correct 1 ms 604 KB Ok
7 Correct 7 ms 4700 KB Ok
8 Correct 0 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 35196 KB Ok
2 Correct 74 ms 35272 KB Ok
3 Correct 73 ms 35280 KB Ok
4 Correct 38 ms 17668 KB Ok
5 Correct 34 ms 17680 KB Ok
6 Correct 18 ms 8928 KB Ok
7 Correct 17 ms 8924 KB Ok
8 Correct 7 ms 4952 KB Ok
9 Correct 8 ms 4700 KB Ok
10 Correct 4 ms 2396 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 348 KB Ok
# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 35276 KB Ok
2 Correct 41 ms 17628 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 344 KB Ok
7 Correct 2 ms 1372 KB Ok
8 Correct 34 ms 17816 KB Ok
9 Correct 20 ms 9148 KB Ok
10 Correct 0 ms 344 KB Ok
11 Correct 1 ms 604 KB Ok
12 Correct 7 ms 4700 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 74 ms 35196 KB Ok
15 Correct 74 ms 35272 KB Ok
16 Correct 73 ms 35280 KB Ok
17 Correct 38 ms 17668 KB Ok
18 Correct 34 ms 17680 KB Ok
19 Correct 18 ms 8928 KB Ok
20 Correct 17 ms 8924 KB Ok
21 Correct 7 ms 4952 KB Ok
22 Correct 8 ms 4700 KB Ok
23 Correct 4 ms 2396 KB Ok
24 Correct 0 ms 348 KB Ok
25 Correct 0 ms 348 KB Ok
26 Correct 1 ms 348 KB Ok
27 Incorrect 81 ms 35276 KB First number in answer is not x 242391 240951
28 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output -1 while solution exists
2 Halted 0 ms 0 KB -