Submission #810646

#	Time	Username	Problem	Language	Result	Execution time	Memory
810646		QwertyPi	DEL13 (info1cup18_del13)	C++14	15 / 100	1095 ms	131072 KiB

del13

#include <bits/stdc++.h>
#define se second
#define fi first

using namespace std;

bool u[200011];

vector<int> ans;

bool query(vector<int> a){
    if(a.size() % 2 != 0) return false;
    deque<pair<int, int>> b;
    map<int, int> mp;
    int c = 0;
    int pa = 0;
    for(auto v : a){
        if(b.empty()) b.push_back({v, ++c}), mp[c]++;
        else if(b.back().second != -1 && b.back().fi + 1 == v){
            b.push_back({v, c}); mp[c]++;
        }else{
            b.push_back({v - 1, -1});
            b.push_back({v, ++c});
            mp[c]++;
        }
    }
    int from = b.size();
    while(b.size() >= 3 && b[b.size() - 3].se == b[b.size() - 2].se && b[b.size() - 2].se == b[b.size() - 1].se){
        ans.push_back(b[b.size() - 2].fi); pair<int, int> p = b[b.size() - 2];
        b.pop_back(); b.pop_back(); b.pop_back(); b.push_back(p); mp[b[b.size() - 1].se] -= 2;
    }

    while(b.size() >= 1){
        if(b.front().se == -1){
            b.pop_front(); continue;
        }
        if(b.size() >= 3 && b[0].se == b[1].se && b[1].se == b[2].se) {
            ans.push_back(b[1].fi); pair<int, int> p = b[1];
            b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
            continue;
        }
        if(b.size() >= 5 && b[1].se == -1 && b[2].se == b[3].se && b[3].se == b[4].se){
            set<int> groups;
            for(int i = 5; i < b.size(); i++) {
                if(b[i].se == -1) continue;
                if(mp[b[i].se] % 2 == 0) groups.insert(b[i].se);
                else break;
            }
            if(groups.size() % 2 == 0){
                ans.push_back(b[3].fi); pair<int, int> p0 = b[0], p1 = b[1], p2 = b[3];
                b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p2); b.push_front(p1); b.push_front(p0);
            }else{
                ans.push_back(b[1].fi); pair<int, int> p = b[1];
                b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
            }
            continue;
        }
        if(b.size() >= 3 && b[1].se == -1){
            ans.push_back(b[1].fi); pair<int, int> p = b[1];
            b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p);
            continue;
        }
        if(b.size() >= 5 && b[0].se == b[1].se && b[0].se != -1 && b[2].se == -1 && b[3].se == b[4].se && b[3].se != -1){
            ans.push_back(b[2].fi); pair<int, int> p1 = b[0], p2 = b[2];
            b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.push_front(p2); b.push_front(p1);
            continue;
        }
        if(from == b.size()) return false; from = b.size();
    }
    return true;
}

int n, k; 
vector<int> p2;
bool solve(){
    cin >> n >> k;
    fill(u, u + n + 1, false);
    vector<int> p;
    for(int i = 0; i < k; i++){
        int v; cin >> v; p.push_back(v); u[v] = true;
    }
    p2 = p;
    vector<int> st; int gap = 2;
    for(int i = 1; i <= n; i++){
        if(!u[i]){
            if(gap >= 2) st.push_back(i), gap = 0;
            else gap = 0;
        }else{
            gap++;
        }
    }
    st.push_back(n + 1);
    int id = 1;
    bool ok = true;
    ans.clear();
    for(int i = 1; i < st.size(); i++){
        vector<int> a;
        for(id; id < st[i]; id++){
            if(!u[id]) a.push_back(id);
        }
        ok &= query(a);
    }

    if(!ok){
        cout << -1 << endl;
        return false;
    }
    cout << ans.size() << endl;
    for(auto i : ans) cout << i << ' '; cout << endl;
    return true;
}

bool solve2(){
    deque<vector<int>> dq; vector<int> ori; for(int i = 1; i <= n; i++) ori.push_back(i); dq.push_back(ori); set<vector<int>> s; s.insert(ori);
    while(!dq.empty()){
        vector<int> v = dq.front(); dq.pop_front();
        if(v == p2) return true;
        for(int i = 1; i < v.size() - 1; i++){
            vector<int> v2;
            if(find(p2.begin(), p2.end(), v[i - 1]) != p2.end() || find(p2.begin(), p2.end(), v[i + 1]) != p2.end()){
                continue;
            }
            for(int j = 0; j < v.size(); j++){
                if(j != i - 1 && j != i + 1){
                    v2.push_back(v[j]);
                }
            }
            if(!s.count(v2)) s.insert(v2), dq.push_back(v2);
        }
    }
    return false;
}

int32_t main(){
    int t; cin >> t;
    while(t--){
        bool b1 = solve();
        bool b2 = solve2();
        assert(b1 == b2);
    }
}

Compilation message (stderr)

del13.cpp: In function 'bool query(std::vector<int>)':
del13.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int i = 5; i < b.size(); i++) {
      |                            ~~^~~~~~~~~~
del13.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(from == b.size()) return false; from = b.size();
      |            ~~~~~^~~~~~~~~~~
del13.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |         if(from == b.size()) return false; from = b.size();
      |         ^~
del13.cpp:68:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |         if(from == b.size()) return false; from = b.size();
      |                                            ^~~~
del13.cpp:16:9: warning: unused variable 'pa' [-Wunused-variable]
   16 |     int pa = 0;
      |         ^~
del13.cpp: In function 'bool solve()':
del13.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 1; i < st.size(); i++){
      |                    ~~^~~~~~~~~~~
del13.cpp:98:13: warning: statement has no effect [-Wunused-value]
   98 |         for(id; id < st[i]; id++){
      |             ^~
del13.cpp:109:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |     for(auto i : ans) cout << i << ' '; cout << endl;
      |     ^~~
del13.cpp:109:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |     for(auto i : ans) cout << i << ' '; cout << endl;
      |                                         ^~~~
del13.cpp: In function 'bool solve2()':
del13.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i = 1; i < v.size() - 1; i++){
      |                        ~~^~~~~~~~~~~~~~
del13.cpp:123:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for(int j = 0; j < v.size(); j++){
      |                            ~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30