제출 #968763

#제출 시각아이디문제언어결과실행 시간메모리
968763marvinthangParking (CEOI22_parking)C++17
100 / 100
288 ms45480 KiB
/************************************* * author: marvinthang * * created: 24.04.2024 10:00:00 * *************************************/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define REPD(i, n) for (int i = (n); i-- > 0; ) #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; ) #define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #ifdef LOCAL #include "debug.h" #else #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define DB(...) 23 #define db(...) 23 #define debug(...) 23 #endif template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } // end of template void process(void) { int n, m; cin >> n >> m; vector <int> bot(m), top(m); vector pos(n + 1, vector(2, -1)); vector <vector <int>> adj(m << 1); vector <int> emp; vector <int> sz(m); REP(i, m) { cin >> bot[i] >> top[i]; if (bot[i]) { ++sz[i]; pos[bot[i]][pos[bot[i]][0] != -1] = i << 1; if (top[i]) { ++sz[i]; pos[top[i]][pos[top[i]][0] != -1] = i << 1 | 1; if (bot[i] != top[i]) { adj[i << 1].push_back(i << 1 | 1); adj[i << 1 | 1].push_back(i << 1); } } } else emp.push_back(i); } auto get_empty = [&] { while (!emp.empty() && sz[emp.back()]) emp.pop_back(); if (emp.empty()) { cout << "-1\n"; exit(0); } return emp.back(); }; FORE(i, 1, n) if (pos[i][0] != (pos[i][1] ^ 1)) { adj[pos[i][0]].push_back(pos[i][1]); adj[pos[i][1]].push_back(pos[i][0]); } vector <pair <int, int>> res; auto move = [&] (int x, int y) { x >>= 1; y >>= 1; res.emplace_back(x, y); if (!--sz[x]) emp.push_back(x); ++sz[y]; }; auto solve_path = [&] (vector <int> &path) { for (int i = 0; i < (int) path.size(); i += 2) { if (path[i + 1] & 1) move(path[i + 1], path[i]); else { int p = path.size(); for (int j = i; j < (int) path.size(); j += 2) if ((path[j] & 1) && (path[j + 1] & 1)) { p = j; break; } if (p < (int) path.size()) { int x = get_empty() << 1; move(path[p], x); move(path[p + 1], x); } for (int j = p - 2; j >= i; j -= 2) move(path[j], path[j + 1]); i = p; } } }; vector <bool> used(m << 1); vector <vector <int>> paths, cycles; vector <int> cnt_pt; REP(i, m + m) if (!used[i] && (int) adj[i].size() == 1) { used[i] = true; vector <int> path {i}; int u = i, p = -1; while (p == -1 || (int) adj[u].size() == 2) { tie(p, u) = pair{u, adj[u][adj[u][0] == p]}; used[u] = true; path.push_back(u); } int cnt = 0; for (int i = 0; i < (int) path.size(); i += 2) if ((path[i] & 1) && (path[i + 1] & 1)) ++cnt; paths.push_back(path); cnt_pt.push_back(cnt); } vector <int> order(paths.size()); iota(ALL(order), 0); sort(ALL(order), [&] (int x, int y) { return cnt_pt[x] < cnt_pt[y]; }); for (int i: order) solve_path(paths[i]); auto del_edge = [&] (int x, int y) { adj[x].erase(find(ALL(adj[x]), y)); adj[y].erase(find(ALL(adj[y]), x)); }; auto solve_cycle = [&] (vector <int> &cycle) { int p = -1; for (int i = 0; i + 1 < (int) cycle.size(); ++i) if ((cycle[i] & 1) && (cycle[i + 1] & 1)) { p = i; break; } if (p != -1) { int x = get_empty() << 1; move(cycle[p], x); move(cycle[p + 1], x); del_edge(!p ? cycle.end()[-2] : cycle[p - 1], cycle[p]); del_edge(cycle[p], cycle[p + 1]); del_edge(cycle[p + 1], p + 2 == (int) cycle.size() ? cycle[1] : cycle[p + 2]); cycle.pop_back(); cycle.erase(cycle.begin() + p); if (p == (int) cycle.size()) cycle.erase(cycle.begin()); else cycle.erase(cycle.begin() + p); rotate(cycle.begin(), cycle.begin() + p, cycle.end()); solve_path(cycle); } else { cycle.pop_back(); if (cycle[0] & 1) rotate(cycle.begin(), cycle.begin() + 1, cycle.end()); if (cycle[0] == (cycle[1] ^ 1)) { rotate(cycle.begin(), cycle.begin() + 1, cycle.end()); reverse(ALL(cycle)); } int x = get_empty() << 1; move(cycle.back(), x); for (int i = 1; i + 2 < (int) cycle.size(); i += 2) move(cycle[i], cycle[i - 1]); move(cycle.end()[-2], x); } }; REP(i, m + m) if (!used[i] && (int) adj[i].size() == 2) { vector <int> cycle; int u = i, p = -1; while (!used[u]) { used[u] = true; cycle.push_back(u); tie(p, u) = pair{u, adj[u][adj[u][0] == p]}; } int cnt = 0; cycle.push_back(cycle[0]); for (int i = 0; i + 1 < (int) cycle.size(); ++i) if ((cycle[i] & 1) && (cycle[i + 1] & 1)) ++cnt; cycles.push_back(cycle); cnt_pt.push_back(cnt); } order.resize(cycles.size()); iota(ALL(order), 0); sort(ALL(order), [&] (int x, int y) { return cnt_pt[x] < cnt_pt[y]; }); for (int i: order) solve_cycle(cycles[i]); cout << res.size() << '\n'; for (auto [x, y]: res) cout << x + 1 << ' ' << y + 1 << '\n'; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); file("parking"); // int t; cin >> t; while (t--) process(); // cerr << "Time elapsed: " << TIME << " s.\n"; return (0^0); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:187:2: note: in expansion of macro 'file'
  187 |  file("parking");
      |  ^~~~
Main.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:187:2: note: in expansion of macro 'file'
  187 |  file("parking");
      |  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...