Submission #760571

#TimeUsernameProblemLanguageResultExecution timeMemory
760571kingfran1907Parking (CEOI22_parking)C++14
0 / 100
70 ms43768 KiB
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 2e5+10; const int base = 31337; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int logo = 20; const int off = 1 << logo; const int treesiz = off << 1; int n, m; int niz[maxn][2]; vector< pair<int, int> > pos[maxn]; vector< pair<int, int> > sol; int nex[maxn], rev[maxn]; bool bio[2 * maxn]; set< int > emps; vector< int > graph[2 * maxn]; vector< vector< int > > chains, cycles; void stop() { printf("-1\n"); exit(0); } bool istop(pair<int, int> t) { int x = t.X; int wh = t.Y; if (wh == 1 || niz[x][1] == 0) return true; return false; } void move(int x, int y) { //printf("moving: %d %d\n", x + 1, y + 1); int ind1 = 0, ind2 = -1; if (niz[x][1] != 0) ind1 = 1; if (niz[y][0] == 0) ind2 = 0; else if (niz[y][1] == 0) ind2 = 1; assert(ind2 >= 0 && niz[x][ind1] != 0); sol.push_back({x + 1, y + 1}); if (ind2 == 0) emps.erase(y); if (ind1 == 0) emps.insert(x); swap(niz[x][ind1], niz[y][ind2]); } void calc_pos() { emps.clear(); for (int i = 0; i < m; i++) { for (int j = 0; j < 2; j++) { if (niz[i][j] != 0) pos[niz[i][j]].push_back({i, j}); } if (niz[i][0] == 0 && niz[i][1] == 0) emps.insert(i); } } vector< int > get_path(int x) { vector< int > v; int ptr = x; int las = -1; while (true) { bio[ptr] = true; v.push_back(ptr); bool flag = false; for (int tren : graph[ptr]) { if (tren != las && !bio[tren]) { las = ptr; ptr = tren; flag = true; break; } } if (!flag) break; } return v; } int price_chain(vector< int > &v) { int cnt = 0; for (int i = 0; i < v.size(); i += 2) { if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++; } if (cnt <= 1) return 0; cnt = 0; reverse(v.begin(), v.end()); for (int i = 0; i < v.size(); i += 2) { if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++; } reverse(v.begin(), v.end()); if (cnt <= 1) return 0; return 1; } void solve_chain(vector< int > &v, int l, int r) { //printf("chain solving\n"); if (l > r) return; for (int i = l; i <= r; i += 2) { if (v[i] % 2 == 1 && v[i + 1] % 2 == 1) { if (emps.empty()) stop(); int ac = *emps.begin(); move(v[i] / 2, ac); move(v[i + 1] / 2, ac); solve_chain(v, l, i - 1); solve_chain(v, i + 2, r); return; } } for (int i = l; i <= r; i += 2) { if (v[i] % 2 == 0 && v[i + 1] % 2 == 0) { for (int j = l; j < i; j += 2) move(v[j + 1] / 2, v[j] / 2); for (int j = r; j > i + 1; j -= 2) move(v[j - 1] / 2, v[j] / 2); move(v[i] / 2, v[i + 1] / 2); return; } } if (v[l + 1] % 2 == 1) { for (int i = l; i <= r; i += 2) move(v[i + 1] / 2, v[i] / 2); } else { for (int i = r; i >= l; i -= 2) move(v[i - 1] / 2, v[i] / 2); } } inline int get(int x) { return niz[x / 2][x % 2]; } int price_cycle(vector< int > &v) { for (int i = 0; i < v.size(); i++) { if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) { vector< int > ne; for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]); return price_chain(ne) + 1; } } return 1; } void solve_cycle(vector< int > &v) { //printf("cycle solving\n"); for (int i = 0; i < v.size(); i++) { if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) { vector< int > ne; for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]); if (emps.empty()) stop(); int x = *emps.begin(); move(v[i] / 2, x); move(v[(i + 1) % v.size()] / 2, x); solve_chain(ne, 0, ne.size() - 1); return; } } if (emps.empty()) stop(); int x = *emps.begin(); int ind = -1; for (int i = 0; i < v.size(); i++) { if (v[i] % 2 == 1) ind = i; } move(v[ind] / 2, x); for (int i = 0; i < v.size() - 1; i += 2) { move(v[(ind + 2 + i) % v.size()] / 2, v[(ind + 1 + i) % v.size()] / 2); } move(v[(ind + v.size() - 1) % v.size()] / 2, x); } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) for (int j = 0; j < 2; j++) scanf("%d", &niz[i][j]); calc_pos(); for (int i = 1; i <= n; i++) { bool flag = true; for (int j = 0; j < 2; j++) { int x = pos[i][j].X; int y = pos[i][j].Y; if (y != 0 || niz[x][1] != 0) flag = false; } if (flag) move(pos[i][0].X, pos[i][1].Y); pos[i].clear(); } calc_pos(); for (int i = 1; i <= n; i++) { int ax = pos[i][0].X; int ay = pos[i][0].Y; int bx = pos[i][1].X; int by = pos[i][1].Y; graph[2 * ax + ay].push_back(2 * bx + by); graph[2 * bx + by].push_back(2 * ax + ay); } for (int i = 0; i < m; i++) { if (niz[i][0] > 0 && niz[i][1] > 0 && niz[i][0] != niz[i][1]) { graph[i * 2].push_back(2 * i + 1); graph[i * 2 + 1].push_back(2 * i); } } for (int i = 0; i < 2 * m; i++) { if (graph[i].size() == 1 && !bio[i]) { vector< int > v = get_path(i); if (v.size() == 2) { if (v[0] / 2 == v[1] / 2) continue; move(v[0] / 2, v[1] / 2); continue; } chains.push_back(v); } } for (int i = 0; i < 2 * m; i++) { if (!bio[i] && graph[i].size() == 2) { vector< int > v = get_path(i); cycles.push_back(v); } } vector< vector< int > > tr; for (auto &iter : chains) { if (price_chain(iter) == 0) solve_chain(iter, 0, iter.size() - 1); else tr.push_back(iter); } for (auto &iter : tr) solve_chain(iter, 0, iter.size() - 1); tr.clear(); for (auto &iter : cycles) { if (price_cycle(iter) == 1) solve_cycle(iter); else tr.push_back(iter); } for (auto &iter : tr) solve_cycle(iter); printf("%d\n", sol.size()); for (auto iter : sol) printf("%d %d\n", iter.X, iter.Y); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int price_chain(std::vector<int>&)':
Main.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < v.size(); i += 2) {
      |                  ~~^~~~~~~~~~
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0; i < v.size(); i += 2) {
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'int price_cycle(std::vector<int>&)':
Main.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
      |                    ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve_cycle(std::vector<int>&)':
Main.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |    for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |  for (int i = 0; i < v.size() - 1; i += 2) {
      |                  ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:250:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  250 |  printf("%d\n", sol.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |          %ld
Main.cpp:183:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |    scanf("%d", &niz[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~
#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...