oj.uz

Submission #197145

# Submission time Handle Problem Language Result Execution time Memory
197145 2020-01-19T09:39:28 Z Pankin DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 760 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first.first
#define sc first.second
#define tr second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>
#define tri pair< pair<int, int>, int >
#define mt(x, y, z) make_pair(make_pair(x, y), z)

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

vector<int> p, ans;
int n, q;

int mask, cur_mask;

bool vis[1 << 19];

bool brute() {
    if (vis[cur_mask])
        return false;
    if (mask == cur_mask)
        return true;
    vis[cur_mask] = true;

    vector<int> cur;
    for (int i = 0; i < n; i++) {
        if ((cur_mask>>i) % 2 == 1)
            cur.pb(i);
    }

    for (int i = 1; i < cur.size() - 1; i++) {
        cur_mask ^= (1 << cur[i - 1]);
        cur_mask ^= (1 << cur[i + 1]);
        ans.pb(cur[i] + 1);

        if (brute())
            return true;

        cur_mask ^= (1 << cur[i - 1]);
        cur_mask ^= (1 << cur[i + 1]);
        ans.pop_back();
    }
    return false;
}

signed main() {
    //fast_io;

    int tests;
    cin >> tests;
    while(tests--) {


        cin >> n >> q;
        p.clear(); p.resize(q);
        for (int i = 0; i < q; i++) {
            cin >> p[i];
            p[i]--;
            mask |= (1 << p[i]);
        }
        cur_mask = (1 << n) - 1;

        if (!brute()) {
            cout << -1 << endl;
        }
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";
        if (ans.size() != 0)
            cout << endl;

        ans.clear(); mask = 0;
        for (int i = 0; i < (1 << n); i++)
            vis[i] = false;
    }

    return 0;
}

/*
1
10 4
1 2 3 7

1110001000

*/

Compilation message

del13.cpp: In function 'bool brute()':
del13.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cur.size() - 1; i++) {
                     ~~^~~~~~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans.size(); i++)
                         ~~^~~~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 256 KB Output isn't correct
2 Incorrect 7 ms 256 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 256 KB Output isn't correct
2 Incorrect 7 ms 256 KB Output isn't correct
3 Execution timed out 1008 ms 632 KB Time limit exceeded
4 Execution timed out 1025 ms 664 KB Time limit exceeded

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 476 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 256 KB Output isn't correct
2 Incorrect 7 ms 256 KB Output isn't correct
3 Execution timed out 1008 ms 632 KB Time limit exceeded
4 Execution timed out 1025 ms 664 KB Time limit exceeded
5 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 256 KB Output isn't correct
2 Incorrect 7 ms 256 KB Output isn't correct
3 Execution timed out 1008 ms 632 KB Time limit exceeded
4 Execution timed out 1025 ms 664 KB Time limit exceeded
5 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 14 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 14 ms 756 KB Execution killed with signal 11 (could be triggered by violating memory limits)