Submission #677482

# Submission time Handle Problem Language Result Execution time Memory
677482 2023-01-03T12:34:11 Z stanislavpolyn Parking (CEOI22_parking) C++17
10 / 100
1584 ms 16876 KB
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e5 + 5;

int n, m;
int a[N][2];
ve<pii> opers;
ve<pii> pos[N];
set<int> emp;

void assertTL(bool f) {
    if (!f) {
        while (1);
    }
}

bool TL() {
    return (double)clock() / CLOCKS_PER_SEC > 1.9;
}

void doOper(int i, int j) {
    assertTL(i != j);
    assertTL(a[i][0]);

    int x = a[i][1] ? a[i][1] : a[i][0];

    int from = a[i][1] ? 1 : 0;
    assertTL(!a[j][1]);
    assertTL(a[j][0] == 0 || a[j][0] == x);

    int idx = -1;
    fr (cur, 0, 1) {
        if (pos[x][cur].fi == i && pos[x][cur].se == from) {
            idx = cur;
            break;
        }
    }
    assertTL(idx != -1);

    if (from == 0) {
        emp.insert(i);
    }

    if (a[j][0] == 0) {
        a[i][from] = 0;
        a[j][0] = x;
        pos[x][idx] = {j, 0};
        emp.erase(j);
    } else {
        assertTL(a[j][0]);
        a[i][from] = 0;
        a[j][1] = x;
        pos[x][idx] = {j, 1};
    }
    opers.pb({i, j});

//    fr (i, 1, m) {
//        if (!a[i][0]) assertTL(emp.count(i));
//        else assertTL(!emp.count(i));
//
//        if (a[i][0]) assertTL(pos[a[i][0]][0] == mp(i, 0) || pos[a[i][0]][1] == mp(i, 0));
//        if (a[i][1]) assertTL(pos[a[i][1]][0] == mp(i, 1) || pos[a[i][1]][1] == mp(i, 1));
//        if (a[i][1]) {
//            assertTL(a[i][0]);
//        }
//    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m;

    assert(n <= int(2e5));
    assert(n >= 1);
    assert(m <= int(2e5));

    fr (i, 1, m) {
        cin >> a[i][0] >> a[i][1];

        assert(a[i][0] >= 0 && a[i][0] <= n);
        assert(a[i][1] >= 0 && a[i][1] <= n);

        if (a[i][0]) {
            pos[a[i][0]].pb({i, 0});
        }
        if (a[i][1]) {
            pos[a[i][1]].pb({i, 1});
        }
    }

    fr (i, 1, n) {
        assert(sz(pos[i]) == 2);
    }

    fr (i, 1, m) {
        if (!a[i][0]) {
            emp.insert(i);
        }
    }

    while (1) {
        bool found = 0;
        int cnt = 0;
        int was = sz(emp);

        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
                cnt++;
                continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

            if (j1 == 1 || !a[i1][1]) {
                if (j2 == 0 && !a[i2][1]) {
                    doOper(i1, i2);
                    found = 1;
                    continue;
                }
            }
            if (j2 == 1 || !a[i2][1]) {
                if (j1 == 0 && !a[i1][1]) {
                    doOper(i2, i1);
                    found = 1;
                }
            }
        }

        assert(sz(emp) >= was);

        if (cnt == n) {
            fr (i, 1, m) {
                if (a[i][0]) {
                    assert(a[i][0] == a[i][1]);
                }
            }

//            assert(0);

            cout << sz(opers) << "\n";
            fe (x, opers) {
                cout << x.fi << " " << x.se << "\n";
            }
            return 0;
        }

        if (found) {
            continue;
        }

        if (!sz(emp)) {
            cout << "-1\n";

            bool have = 0;
            fr (i, 1, m) {
                fr (j, 1, m) {
                    if (i == j) continue;
                    if (!a[i][0]) continue;
                    if (a[j][1]) continue;

                    int x = a[i][1] ? a[i][1] : a[i][0];
                    if (!a[j][0] || a[j][0] == x) {
                        have = 1;
                    }
                }
            }

            assert(!have);

            return 0;
        }

        bool ok = 0;
        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
               continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

            if (j1 != j2) {
                ok = 1;

                if (j1 == 0) {
                    if (sz(emp)) {
                        int to = *emp.begin();
                        doOper(i1, to);
                        doOper(i2, i1);
                        found = 1;
                        break;
                    }
                }
                if (j2 == 0) {
                    if (sz(emp)) {
                        int to = *emp.begin();
                        doOper(i2, to);
                        doOper(i1, i2);
                        found = 1;
                        break;
                    }
                }
            }
        }

        if (found) {
            continue;
        }

        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
                continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

            if (j1 == 1 && j2 == 1) {
                if (sz(emp)) {
                    int to = *emp.begin();
                    doOper(i1, to);
                    doOper(i2, to);
                    found = 1;
                }
            }
        }

        if (found) {
            continue;
        }

//        cout << "YEP HERE\n";
//        fr (i, 1, n) {
//            if (pos[i][0].fi == pos[i][1].fi) {
//               continue;
//            }
//
//            if (sz(emp)) {
//                assert(pos[i][0].se != pos[i][1].se);
//            }
//        }


//        assert(ok);

        if (!found) {
            bool have = 0;
            fr (i, 1, m) {
                fr (j, 1, m) {
                    if (i == j) continue;
                    if (!a[i][0]) continue;
                    if (a[j][1]) continue;

                    int x = a[i][1] ? a[i][1] : a[i][0];
                    if (!a[j][0] || a[j][0] == x) {
                        have = 1;
                    }
                }
            }

            assert(!have);

            cout << "-1\n";
            return 0;
        }
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:224:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  224 |         bool ok = 0;
      |              ^~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 5032 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1584 ms 16876 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 5032 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Incorrect 1584 ms 16876 KB Output isn't correct
12 Halted 0 ms 0 KB -