oj.uz

Submission #173946

# Submission time Handle Problem Language Result Execution time Memory
173946 2020-01-05T20:12:56 Z emil_physmath "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 321 ms 8324 KB 
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
typedef unsigned int uint;

int n;
uint a[1 << 20];
bool used[1 << 20];
bool is[1 << 20];
int changeInd[1 << 20];

ostream& PrintBin(uint a)
{
    for (int i = n - 1; i >= 0; --i)
        cout << (bool)(a & (1 << i));
    return cout;
}
int Bits(uint a)
{
    int res = 0;
    while (a)
    {
        res += a & 1;
        a >>= 1;
    }
    return res;
}
void Print(string s_str)
{
    uint s = 0;
    reverse(s_str.begin(), s_str.end());
    for (int i = 0; i < s_str.length(); ++i)
        if (s_str[i] == '1')
            s += (1U << i);
    cout << (1 << n) << endl;
    for (auto it = find(a, a + (1 << n), s); it != a + (1 << n); ++it)
        PrintBin(*it) << '\n';
    for (int i = 0; a[i] != s; ++i)
        PrintBin(a[i]) << '\n';
}
int main()
{
    int k, t;
    cin >> n >> k >> t;
    if (k % 2 == 0)
    {
        cout << -1;
        exit(0);
    }
    vector<uint> changes;
    for (uint mask = 0; mask < (1U << n); ++mask)
        if (Bits(mask) == k)
        {
            changes.push_back(mask);
            is[mask] = true;
            // PrintBin(mask) << endl;
        }
    random_shuffle(changes.begin(), changes.end());
    string s;
    cin >> s;
    int top = 1;
    used[0] = true;
    while (top)
    {
        /*cerr << "top = " << top << endl;
        for (int i = 0; i < top; ++i)
            PrintBin(a[i]) << '\n';*/
        if (top == (1 << n))
        {
            if (is[a[0] ^ a[top - 1]])
            {
                Print(s);
                exit(0);
            }
            else
            {
                if (++changeInd[top - 1] == changes.size())
                {
                    cout << "-1\n";
                    exit(0);
                }
                used[a[top - 1]] = false;
                --top;
            }
        }
        if (changeInd[top] == changes.size())
        {
            changeInd[top] = 0;
            used[a[top - 1]] = false;
            --top;
        }
        else
        {
            uint newTop = a[top - 1] ^ changes[changeInd[top]];
            // cerr << "XORed with " << changes[changeInd[top]] << endl;
            // cerr << "newTop: " << newTop << endl;
            if (!used[newTop])
            {
                a[top] = newTop;
                ++changeInd[top];
                used[newTop] = true;
                ++top;
            }
            else
                ++changeInd[top];
        }
    }
    cout << -1 << endl;
}

Compilation message

lyuboyn.cpp: In function 'void Print(std::__cxx11::string)':
lyuboyn.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s_str.length(); ++i)
                     ~~^~~~~~~~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:79:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (++changeInd[top - 1] == changes.size())
                     ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
lyuboyn.cpp:88:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (changeInd[top] == changes.size())
             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 424 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 380 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 7664 KB Ok
2 Correct 146 ms 3960 KB Ok
3 Correct 3 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 9 ms 504 KB Ok
3 Correct 146 ms 3960 KB Ok
4 Correct 70 ms 2040 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 35 ms 1272 KB Ok
8 Correct 3 ms 380 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 8292 KB Ok
2 Correct 313 ms 8036 KB Ok
3 Correct 311 ms 7792 KB Ok
4 Correct 150 ms 4248 KB Ok
5 Correct 147 ms 4084 KB Ok
6 Correct 71 ms 2168 KB Ok
7 Correct 70 ms 2096 KB Ok
8 Correct 34 ms 1144 KB Ok
9 Correct 35 ms 1272 KB Ok
10 Correct 17 ms 760 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 3 ms 380 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 7664 KB Ok
2 Correct 146 ms 3960 KB Ok
3 Correct 3 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 9 ms 504 KB Ok
8 Correct 146 ms 3960 KB Ok
9 Correct 70 ms 2040 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 35 ms 1272 KB Ok
13 Correct 3 ms 380 KB Ok
14 Correct 314 ms 8292 KB Ok
15 Correct 313 ms 8036 KB Ok
16 Correct 311 ms 7792 KB Ok
17 Correct 150 ms 4248 KB Ok
18 Correct 147 ms 4084 KB Ok
19 Correct 71 ms 2168 KB Ok
20 Correct 70 ms 2096 KB Ok
21 Correct 34 ms 1144 KB Ok
22 Correct 35 ms 1272 KB Ok
23 Correct 17 ms 760 KB Ok
24 Correct 3 ms 376 KB Ok
25 Correct 3 ms 380 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 306 ms 7936 KB Ok
28 Correct 150 ms 4028 KB Ok
29 Correct 313 ms 8228 KB Ok
30 Correct 17 ms 760 KB Ok
31 Correct 3 ms 376 KB Ok
32 Correct 9 ms 504 KB Ok
33 Correct 34 ms 1144 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 380 KB Ok
38 Correct 150 ms 3968 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3960 KB Ok
2 Correct 306 ms 7860 KB Ok
3 Correct 321 ms 8324 KB Ok
4 Correct 18 ms 760 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 35 ms 1272 KB Ok
7 Correct 308 ms 8080 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 70 ms 2040 KB Ok
12 Correct 150 ms 4200 KB Ok