Submission #884284

#	Time	Username	Problem	Language	Result	Execution time	Memory
884284		Kevin_Zhang_TW	Parking (CEOI22_parking)	C++17	50 / 100	198 ms	44360 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

const int MAX_N = 300010;

int n, m;
vector<int> stk[MAX_N], emp;
vector<int> at[MAX_N];
void fail() {
  cout << -1 << '\n';
  exit(0);
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 0;i < m;++i) {
    int b, t;
    cin >> b >> t;
    for (int j : {b, t}) if (j) {
      stk[i].pb(j);
      at[j].pb(i);
    }
    if (b == 0) emp.pb(i);
  }

  vector<pair<int,int>> res;
  // all full or empty
//
//  vector<pair<int,int>> ud;
  auto hp = [&]() {
    DE("stk");
    for (int i = 0;i < m;++i)
      debug(AI(stk[i]));
  };
  auto atob = [&](int a, int b) {
    int v = stk[a].back(); stk[a].pop_back();
    stk[b].pb(v);
    *find(AI(at[v]), a) = b;
    res.pb(a, b);
  };
  auto other = [&](int x, int p) {
    return at[x][0] + at[x][1] - p;
  };
  auto shift = [&](int p) {
    assert(stk[p].size() == 1);
    int v = stk[p][0], o = other(v, p);
    while (stk[o].size() == 2 && stk[o][1] == v) {
      atob(o, p);
      p = o;
      v = stk[p][0];
      o = other(v, p);
    }
    return p;
  };
  auto eqtop = [&](int p) {
    int v = stk[p][1], o = other(v, p);
    while (stk[o][0] == v) {
      p = o;
      v = stk[p][1], o = other(v, p);
    }
    return p;
  };
  function<void(int)> take_care = [&](int p) {
    if (emp.empty()) fail();
    if (stk[p].empty()) {
      emp.pb(p);
      return;
    }
    assert(stk[p].size() == 1);
    int v = stk[p][0];
    int e = emp.back(), o = other(v, p);
    if (stk[o].size() == 1 || stk[o][1] == v) {
      atob(o, p);
      take_care(o);
      return;
    }
    int g = eqtop(o);
    atob(g, e);
    shift(g);
    atob(o, p);
    emp.back() = o;
    take_care(e);
  };

  function<void(int)> no_more_care = [&](int p) {
    if (stk[p].empty()) {
      emp.pb(p);
      return;
    }
    assert(stk[p].size() == 1);
    int v = stk[p][0];
    int o = other(v, p);
    if (stk[o].back() == v) {
      atob(o, p);
      no_more_care(o);
    }
  };

  for (int i = 0;i < m;++i) if (stk[i].size() == 1) {
    no_more_care(i);
  }
  //hp();
//  for (int i = 0;i < m;++i) if (stk[i].size() == 1)
//    take_care(i);
//    int x = stk[i][0];
//    if (stk[other(x, i)].back() == x)
//      take_
  for (int i = 1;i <= n;++i) {
    int a = at[i][0], b = at[i][1];
    if (a == b) continue;
    if (stk[a][1] == i && stk[b][1] == i) {
      if (emp.empty()) fail();
      int e = emp.back(); emp.pop_back();
      atob(a, e);
      atob(b, e);
      a = shift(a), b = shift(b);
      if (stk[a][0] == stk[b][0]) {
        atob(a, b);
        emp.pb(a);
      } else {
        take_care(a);
      }
    }
  }

  for (int i = 1;i <= n;++i) {
    int a = at[i][0], b = at[i][1];
    if (a == b) continue;
    if (emp.empty()) fail();
    if (stk[a][0] != i) swap(a, b);
    // stk[a][0] = i
    int e = emp.back();
    atob(a, e);
    int g = shift(a);
    atob(e, g);
    // must be one up and one down
  }
  for (int i = 1;i <= n;++i) assert(at[i][0] == at[i][1]);

  cout << res.size() << '\n';
  for (auto [a, b] : res) {
    ++a, ++b;
    cout << a << ' ' << b << '\n';
  }
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:51:5: note: in expansion of macro 'DE'
   51 |     DE("stk");
      |     ^~
Main.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Main.cpp:53:7: note: in expansion of macro 'debug'
   53 |       debug(AI(stk[i]));
      |       ^~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:50:8: warning: variable 'hp' set but not used [-Wunused-but-set-variable]
   50 |   auto hp = [&]() {
      |        ^~

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