oj.uz

Submission #197144

# Submission time Handle Problem Language Result Execution time Memory
197144 2020-01-19T09:37:01 Z Pankin DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 131076 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 brute() {
    if (mask == cur_mask)
        return 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;
    }

    return 0;
}

/*
1
10 4
1 2 3 7

1110001000

*/

Compilation message

del13.cpp: In function 'bool brute()':
del13.cpp:59: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:95: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 20 ms 376 KB Output isn't correct
2 Incorrect 10 ms 376 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 376 KB Output isn't correct
2 Incorrect 10 ms 376 KB Output isn't correct
3 Execution timed out 1016 ms 360 KB Time limit exceeded
4 Execution timed out 1051 ms 376 KB Time limit exceeded

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 411 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Execution timed out 1058 ms 256 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 376 KB Output isn't correct
2 Incorrect 10 ms 376 KB Output isn't correct
3 Execution timed out 1016 ms 360 KB Time limit exceeded
4 Execution timed out 1051 ms 376 KB Time limit exceeded
5 Runtime error 426 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 425 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Execution timed out 1004 ms 256 KB Time limit exceeded

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 376 KB Output isn't correct
2 Incorrect 10 ms 376 KB Output isn't correct
3 Execution timed out 1016 ms 360 KB Time limit exceeded
4 Execution timed out 1051 ms 376 KB Time limit exceeded
5 Runtime error 426 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 425 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Execution timed out 1004 ms 256 KB Time limit exceeded
8 Runtime error 399 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 415 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 417 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 378 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)