답안 #861508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861508	2023-10-16T11:39:07 Z	Alfraganus	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	52 / 100	74 ms	35280 KB

lyuboyn

#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)
    {
        int x = node;
        for (int i = 0; i < n; i++)
        {
            x ^= (1 << i);
            if (!used[x] and dfs(x, step + 1))
            {
                ans.push_back(node);
                return true;
            }
            x ^= (1 << i);
        }
    }
    else if (k == 3)
    {
        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 (!used[y] and dfs(y, step + 1))
                    {
                        ans.push_back(node);
                        return true;
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if (k == 5)
    {
        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 (!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;
                            }
                            y ^= (1 << i2);
                        }
                        y ^= (1 << i1);
                    }
                    y ^= (1 << x);
                }
                y ^= (1 << j);
            }
            y ^= (1 << i);
        }
    }
    else if (k == 7)
    {
        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 (!used[y] and dfs(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 or n == k)
    {
        cout << -1;
        return;
    }
    bool flag = 2 * k > n;
    if (2 * k > n)
        k = n - k;
    if(k % 2 == 0 or (flag and sx != 0)){
        cout << -1;
        return;
    }
    used.resize((1 << n));
    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:197:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |             for(int i = 0; i < ans.size(); i ++){
      |                            ~~^~~~~~~~~~~~
lyuboyn.cpp:224:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for (int i = 0; i < ans.size(); i++)
      |                             ~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Ok

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Ok

Subtask #3
3.0 / 3.0

#	결과	메모리	Grader output
1	Correct	348 KB	Ok
2	Correct	348 KB	Ok
3	Correct	348 KB	Ok
4	Correct	348 KB	Ok
5	Correct	348 KB	Ok
6	Correct	348 KB	Ok
7	Correct	348 KB	Ok
8	Correct	348 KB	Ok

Subtask #4
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	35120 KB	Ok
2	Correct	32 ms	17604 KB	Ok
3	Correct	0 ms	348 KB	Ok
4	Correct	0 ms	348 KB	Ok
5	Correct	0 ms	348 KB	Ok

Subtask #5
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Ok
2	Correct	2 ms	1448 KB	Ok
3	Correct	39 ms	17624 KB	Ok
4	Correct	17 ms	8928 KB	Ok
5	Correct	1 ms	348 KB	Ok
6	Correct	1 ms	604 KB	Ok
7	Correct	7 ms	4732 KB	Ok
8	Correct	0 ms	348 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	74 ms	35280 KB	Ok
2	Correct	71 ms	35180 KB	Ok
3	Correct	72 ms	35164 KB	Ok
4	Correct	37 ms	17628 KB	Ok
5	Correct	33 ms	17620 KB	Ok
6	Correct	17 ms	8928 KB	Ok
7	Correct	16 ms	8928 KB	Ok
8	Correct	8 ms	4956 KB	Ok
9	Correct	8 ms	4696 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

Subtask #7
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	35120 KB	Ok
2	Correct	32 ms	17604 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	2 ms	1448 KB	Ok
8	Correct	39 ms	17624 KB	Ok
9	Correct	17 ms	8928 KB	Ok
10	Correct	1 ms	348 KB	Ok
11	Correct	1 ms	604 KB	Ok
12	Correct	7 ms	4732 KB	Ok
13	Correct	0 ms	348 KB	Ok
14	Correct	74 ms	35280 KB	Ok
15	Correct	71 ms	35180 KB	Ok
16	Correct	72 ms	35164 KB	Ok
17	Correct	37 ms	17628 KB	Ok
18	Correct	33 ms	17620 KB	Ok
19	Correct	17 ms	8928 KB	Ok
20	Correct	16 ms	8928 KB	Ok
21	Correct	8 ms	4956 KB	Ok
22	Correct	8 ms	4696 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	1 ms	348 KB	Output -1 while solution exists
28	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	348 KB	Output -1 while solution exists
2	Halted	0 ms	0 KB	-