oj.uz

Submission #317544

# Submission time Handle Problem Language Result Execution time Memory
317544 2020-10-30T01:54:55 Z casperwang DEL13 (info1cup18_del13) C++14
30 / 100
 19 ms 2184 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

const int MAXN = 100000;
stack <int> ans;

bool solve(vector <pii> &arr) {
  vector <int> cnt(arr.size()+1);
  for (int i = 0; i < arr.size(); i++)
    cnt[i] = arr[i].ss - arr[i].ff + 1;
  for (int i = 0; i+1 < arr.size(); i++) {
    if (cnt[i] % 2) {
      ans.push(arr[i].ss+1);
      cnt[i]--, cnt[i+1]--;
    }
  }
  if (cnt[arr.size()-1] % 2) return 0;
  stack <int> tmp;
  for (int i = 0; i <= arr.size(); i++) {
    if (cnt[i] && arr[i].ss - arr[i].ff + 1 == 2) {
      tmp.push(i);
    } else if (!cnt[i]) {
      while (tmp.size()) {
        ans.push(arr[tmp.top()].ff-1);
        ans.push(arr[tmp.top()].ff-1);
        cnt[tmp.top()] -= 2;
        if (tmp.size() > 1) {
          tmp.pop();
          cnt[tmp.top()] -= 2;
          tmp.pop();
        } else {
          if (!tmp.top() || !cnt[tmp.top()-1]) return 0;
          cnt[tmp.top()-1] -= 2;
          tmp.pop();
        }
      }
    } else {
      if (tmp.size() % 2) {
        ans.push(arr[i].ff-1);
        ans.push(arr[i].ff-1);
        cnt[i] -= 2;
        cnt[tmp.top()] -= 2;
        tmp.pop();
      }
      while (tmp.size()) {
        ans.push(arr[tmp.top()].ff-1);
        ans.push(arr[tmp.top()].ff-1);
        cnt[tmp.top()] -= 2;
        tmp.pop();
        cnt[tmp.top()] -= 2;
        tmp.pop();
      }
      if (i < arr.size() && cnt[i] == arr[i].ss - arr[i].ff + 1) {
        if (i && cnt[i-1]) {
          ans.push(arr[i].ff-1);
          ans.push(arr[i].ff-1);
          cnt[i] -= 2;
          cnt[i-1] -= 2;
        } else if (cnt[i+1]) {
          ans.push(arr[i].ss+1);
          ans.push(arr[i].ss+1);
          cnt[i] -= 2;
          cnt[i+1] -= 2;
        } else return 0;
      }
    }
  }
  for (int i = 0; i < arr.size(); i++) {
    while (cnt[i]) {
      ans.push((arr[i].ff + arr[i].ss) / 2);
      cnt[i] -= 2;
    }
  }
  return 1;
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int a;
    vector <int> p(n+1);
    for (int i = 1; i <= k; i++)
      cin >> a, p[a] = 1;
    int l = 1, r = 0, now = 0;
    vector <vector<pii>> arr(1);
    for (int i = 1; i <= n; i++) {
      if (p[i]) {
        if (r >= l) arr[now].pb(pii(l, r));
        else arr.pb(vector<pii>()), now++;
        l = i+1;
      } else r = i;
    }
    if (r >= l) arr[now].pb(pii(l, r));
    bool tf = 1;
    for (vector <pii> v : arr) {
      if (!solve(v)) {
        tf = 0;
        break;
      }
    }
    if (!tf) {
      cout << -1 << "\n";
      while (ans.size()) ans.pop();
    } else {
      cout << ans.size() << "\n";
      while (ans.size()) {
        cout << ans.top(), ans.pop();
        cout << "\n "[ans.size()>0];
      }
    }
  }
}

Compilation message

del13.cpp: In function 'bool solve(std::vector<std::pair<int, int> >&)':
del13.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for (int i = 0; i < arr.size(); i++)
      |                   ~~^~~~~~~~~~~~
del13.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (int i = 0; i+1 < arr.size(); i++) {
      |                   ~~~~^~~~~~~~~~~~
del13.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int i = 0; i <= arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
del13.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |       if (i < arr.size() && cnt[i] == arr[i].ss - arr[i].ff + 1) {
      |           ~~^~~~~~~~~~~~
del13.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int i = 0; i < arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 8 ms 384 KB Output isn't correct
4 Incorrect 10 ms 384 KB Output isn't correct

Subtask #3
15.0 / 15.0

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

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 8 ms 384 KB Output isn't correct
4 Incorrect 10 ms 384 KB Output isn't correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 288 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 8 ms 384 KB Output isn't correct
4 Incorrect 10 ms 384 KB Output isn't correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 288 KB Output is correct
8 Incorrect 17 ms 1012 KB Output isn't correct
9 Incorrect 19 ms 1712 KB Output isn't correct
10 Correct 13 ms 1300 KB Output is correct
11 Incorrect 13 ms 2184 KB Output isn't correct