oj.uz

Submission #173937

# Submission time Handle Problem Language Result Execution time Memory
173937 2020-01-05T20:08:10 Z emil_physmath "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 1000 ms 8204 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;
    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:74:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (++changeInd[top - 1] == changes.size())
                     ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
lyuboyn.cpp:83: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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 7780 KB Ok
2 Correct 144 ms 3960 KB Ok
3 Correct 3 ms 504 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 145 ms 3956 KB Ok
4 Correct 70 ms 2168 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 34 ms 1272 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 8204 KB Ok
2 Correct 313 ms 8176 KB Ok
3 Correct 309 ms 7964 KB Ok
4 Correct 149 ms 4220 KB Ok
5 Correct 148 ms 4088 KB Ok
6 Correct 70 ms 2168 KB Ok
7 Correct 69 ms 2040 KB Ok
8 Correct 34 ms 1272 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 376 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 7780 KB Ok
2 Correct 144 ms 3960 KB Ok
3 Correct 3 ms 504 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 145 ms 3956 KB Ok
9 Correct 70 ms 2168 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 34 ms 1272 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 313 ms 8204 KB Ok
15 Correct 313 ms 8176 KB Ok
16 Correct 309 ms 7964 KB Ok
17 Correct 149 ms 4220 KB Ok
18 Correct 148 ms 4088 KB Ok
19 Correct 70 ms 2168 KB Ok
20 Correct 69 ms 2040 KB Ok
21 Correct 34 ms 1272 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 376 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 309 ms 7696 KB Ok
28 Correct 152 ms 4084 KB Ok
29 Correct 320 ms 8184 KB Ok
30 Correct 18 ms 760 KB Ok
31 Correct 3 ms 376 KB Ok
32 Correct 9 ms 504 KB Ok
33 Correct 35 ms 1272 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 376 KB Ok
38 Correct 148 ms 3980 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 4040 KB Ok
2 Correct 305 ms 7736 KB Ok
3 Correct 313 ms 8104 KB Ok
4 Correct 17 ms 760 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 35 ms 1272 KB Ok
7 Correct 307 ms 7956 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 149 ms 3960 KB Ok