oj.uz

Submission #810617

# Submission time Handle Problem Language Result Execution time Memory
810617 2023-08-06T12:26:15 Z QwertyPi DEL13 (info1cup18_del13) C++14
15 / 100
 15 ms 2252 KB 
#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;
    int c = 0;
    for(auto v : a){
        if(b.empty()) b.push_back({v, ++c});
        else if(b.back().second != -1 && b.back().fi + 1 == v){
            b.push_back({v, c});
        }else{
            b.push_back({v - 1, -1});
            b.push_back({v, ++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);
    }

    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() >= 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); ans.push_back(b[2].fi); pair<int, int> p = b[0];
            b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front(); b.pop_front();
            continue;
        }
        if(from == b.size()) return false; from = b.size();
    }
    return true;
}

void solve(){
    int n, k; 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;
    }
    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;
    if(st.size() > 2){
        ok = false;
    }else{
        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;
    }
    cout << ans.size() << endl;
    for(auto i : ans) cout << i << ' '; cout << endl;
}
int32_t main(){
    int t; cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

del13.cpp: In function 'bool query(std::vector<int>)':
del13.cpp:45:76: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   45 |             ans.push_back(b[2].fi); ans.push_back(b[2].fi); pair<int, int> p = b[0];
      |                                                                            ^
del13.cpp:49: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]
   49 |         if(from == b.size()) return false; from = b.size();
      |            ~~~~~^~~~~~~~~~~
del13.cpp:49:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |         if(from == b.size()) return false; from = b.size();
      |         ^~
del13.cpp:49:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |         if(from == b.size()) return false; from = b.size();
      |                                            ^~~~
del13.cpp: In function 'void solve()':
del13.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = 1; i < st.size(); i++){
      |                        ~~^~~~~~~~~~~
del13.cpp:79:17: warning: statement has no effect [-Wunused-value]
   79 |             for(id; id < st[i]; id++){
      |                 ^~
del13.cpp:91:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   91 |     for(auto i : ans) cout << i << ' '; cout << endl;
      |     ^~~
del13.cpp:91:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |     for(auto i : ans) cout << i << ' '; cout << endl;
      |                                         ^~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 9 ms 388 KB Output isn't correct
4 Incorrect 9 ms 320 KB Output isn't correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 4 ms 1252 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 9 ms 388 KB Output isn't correct
4 Incorrect 9 ms 320 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 9 ms 388 KB Output isn't correct
4 Incorrect 9 ms 320 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 10 ms 1484 KB Output isn't correct
9 Incorrect 12 ms 1484 KB Output isn't correct
10 Incorrect 11 ms 1228 KB Output isn't correct
11 Incorrect 15 ms 2252 KB Output isn't correct