oj.uz

Submission #145909

# Submission time Handle Problem Language Result Execution time Memory
145909 2019-08-21T10:56:53 Z davitmarg "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 319 ms 21140 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int cnt(int num)
{
    int res=0;
    while(num)
    {
        res+=num%2;
        num/=2;
    }
    return res;
}

vector<int> dirs,path;
int n,k,t,s,used[(1<<18)+10],is[(1<<18)+10]; 

void print(int num)
{
    string s;
    for(int i=0;i<n;i++)
    {
        s+=(char)(num%2+'0');
        num/=2;
    }
    reverse(all(s));
    for(int i=0;i<s.length();i++)
        printf("%c",s[i]);
    putchar(10);
}

void dfs(int v)
{
    vector<int>& d=dirs;
    path.PB(v);
    used[v]=1;
    if(path.size()==(1<<n) && is[(path[0]^v)])
    {
        cout<<path.size()<<endl;
        for(int i=0;i<path.size();i++)
            print(path[i]);
        exit(0);
    }
    //random_shuffle(all(d));
    for(int i=0;i<d.size();i++)
    {
        int to=v^d[i];
        if(used[to])
            continue;
        dfs(to);
    }
    path.pop_back();
    used[v]=0;
}


int main()
{
    cin>>n>>k>>t;
    for(int i=0;i<n;i++)
    {
        char x;
        cin>>x;
        s=s*2+(x-'0');
    }
    if(k%2==0)
    {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<(1<<n);i++)
        if(cnt(i)==k)
        {
            dirs.PB(i);
            is[i]=1;
        }
    dfs(s);
    cout<<-1<<endl;
	return 0;
}
 
/*

5 3 0
00000


*/

Compilation message

lyuboyn.cpp: In function 'void print(int)':
lyuboyn.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.length();i++)
                 ~^~~~~~~~~~~
lyuboyn.cpp: In function 'void dfs(int)':
lyuboyn.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(path.size()==(1<<n) && is[(path[0]^v)])
        ~~~~~~~~~~~^~~~~~~~
lyuboyn.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<path.size();i++)
                     ~^~~~~~~~~~~~
lyuboyn.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<d.size();i++)
                 ~^~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 252 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 256 KB Ok
6 Correct 2 ms 256 KB Ok
7 Correct 2 ms 256 KB Ok
8 Correct 2 ms 256 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 19884 KB Ok
2 Correct 145 ms 10088 KB Ok
3 Correct 3 ms 404 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 1016 KB Ok
3 Correct 143 ms 10408 KB Ok
4 Correct 68 ms 5356 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 4 ms 504 KB Ok
7 Correct 33 ms 2936 KB Ok
8 Correct 2 ms 380 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 21140 KB Ok
2 Correct 299 ms 20844 KB Ok
3 Correct 302 ms 20204 KB Ok
4 Correct 143 ms 10736 KB Ok
5 Correct 145 ms 10224 KB Ok
6 Correct 69 ms 5360 KB Ok
7 Correct 69 ms 5184 KB Ok
8 Correct 35 ms 2808 KB Ok
9 Correct 33 ms 2936 KB Ok
10 Correct 17 ms 1656 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 314 ms 19884 KB Ok
2 Correct 145 ms 10088 KB Ok
3 Correct 3 ms 404 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 1016 KB Ok
8 Correct 143 ms 10408 KB Ok
9 Correct 68 ms 5356 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 4 ms 504 KB Ok
12 Correct 33 ms 2936 KB Ok
13 Correct 2 ms 380 KB Ok
14 Correct 312 ms 21140 KB Ok
15 Correct 299 ms 20844 KB Ok
16 Correct 302 ms 20204 KB Ok
17 Correct 143 ms 10736 KB Ok
18 Correct 145 ms 10224 KB Ok
19 Correct 69 ms 5360 KB Ok
20 Correct 69 ms 5184 KB Ok
21 Correct 35 ms 2808 KB Ok
22 Correct 33 ms 2936 KB Ok
23 Correct 17 ms 1656 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 303 ms 19924 KB Ok
28 Correct 143 ms 10480 KB Ok
29 Correct 319 ms 20972 KB Ok
30 Correct 16 ms 1528 KB Ok
31 Correct 3 ms 376 KB Ok
32 Correct 9 ms 1016 KB Ok
33 Correct 32 ms 2808 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 142 ms 10096 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 10060 KB Ok
2 Correct 298 ms 19804 KB Ok
3 Correct 298 ms 20972 KB Ok
4 Correct 17 ms 1656 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 33 ms 2808 KB Ok
7 Correct 303 ms 20712 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 68 ms 5148 KB Ok
12 Correct 154 ms 10596 KB Ok