Submission #634772

#	Time	Username	Problem	Language	Result	Execution time	Memory
634772		Ooops_sorry	Parking (CEOI22_parking)	C++14	100 / 100	867 ms	189304 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> a[i][j];
        }
    }
    int cnt = 0, cur = 0;
    vector<deque<pair<int,int>>> pos(n + 1);
    vector<vector<int>> val(m, vector<int>(2)), g(2 * n);
    vector<int> num(2 * n), ord, index(2 * n);
    vector<bool> is_top(2 * n), used(2 * n);
    deque<int> cond, emp, non_emp;
    for (int i = 1; i <= n; i++) {
        cond.pb(i);
    }
    for (int i = 0; i < m; i++) {
        emp.pb(i);
        non_emp.pb(i);
    }
    for (int i = 0; i < m; i++) {
        while (a[i].size() > 0 && a[i].back() == 0) {
            a[i].pop_back();
        }
    }
    for (int i = 0; i < m; i++) {
        if (a[i].size() > 0) {
            index[cur] = i;
            num[cur] = a[i][0];
            val[i][0] = cur++;
            pos[a[i][0]].pb({i, 0});
        }
        if (a[i].size() > 1) {
            index[cur] = i;
            num[cur] = a[i][1];
            is_top[cur] = 1;
            val[i][1] = cur++;
            pos[a[i][1]].pb({i, 1});
        }
        if (a[i].size() > 1) {
            int x = val[i][0], y = val[i][1];
            g[x].pb(y);
            g[y].pb(x);
        }
    }
    for (int i = 1; i <= n; i++) {
        int x = val[pos[i][0].first][pos[i][0].second];
        int y = val[pos[i][1].first][pos[i][1].second];
        g[x].pb(y);
        g[y].pb(x);
    }
    for (int j = 1; j <= 2; j++) {
        for (int i = 0; i < 2 * n; i++) {
            if (used[i]) continue;
            if (g[i].size() <= j) {
                deque<int> q{i};
                used[i] = 1;
                int cnt = 0;
                set<int> st;
                while (q.size() > 0) {
                    int v = q.back();
                    st.insert(index[v]);
                    q.pop_back();
                    cnt++;
                    for (auto to : g[v]) {
                        if (is_top[v] && is_top[to]) {
                            ord.pb(num[v]);
                        }
                        if (!used[to]) {
                            used[to] = 1;
                            q.pb(to);
                        }
                    }
                }
            }
        }
    }
    reverse(ord.begin(), ord.end());
    vector<pair<int,int>> ans;
    auto upd = [&](int i, int j) -> void {
        assert(i != j && a[i].size() > 0 && (a[j].size() == 0 || (a[j].size() == 1 && a[i].back() == a[j][0])));
        for (auto to : a[i]) {
            cond.pb(to);
        }
        for (auto to : a[j]) {
            cond.pb(to);
        }
        emp.pb(i);
        non_emp.pb(j);
        int val = a[i].back();
        if (pos[val][0].first == i) {
            pos[val].pop_front();
        } else {
            pos[val].pop_back();
        }
        pos[val].pb({j, a[j].size()});
        a[i].pop_back();
        a[j].pb(val);
        ans.pb({i, j});
    };
    while (1) {
        bool op = 0;
        while (cond.size() > 0) {
            int type = cond.back();
            cond.pop_back();
            if (pos[type][0].first == pos[type][1].first) continue;
            if (pos[type][0].second != 0) {
                swap(pos[type][0], pos[type][1]);
            }
            int i = pos[type][0].first, j = pos[type][1].first;
            if (pos[type][0].second == 0 && a[i].size() == 1 && a[j].size() == pos[type][1].second + 1) {
                upd(j, i);
                op = 1;
                break;
            }
        }
        if (op) continue;
        while (emp.size() > 0) {
            int i = emp.front();
            if (a[i].size() == 0) {
                break;
            }
            emp.pop_front();
        }
        if (ord.size() > 0) {
            if (emp.size() == 0) {
                cout << -1 << endl;
                return 0;
            }
            int type = ord.back();
            ord.pop_back();
            if (pos[type][0].first == pos[type][1].first) continue;
            upd(pos[type][1].first, emp[0]);
            upd(pos[type][0].first, emp[0]);
            continue;
        }
        while (non_emp.size() > 0) {
            int i = non_emp.front();
            if (a[i].size() == 2 && (a[i][0] != a[i][1])) {
                break;
            }
            non_emp.pop_front();
        }
        if (non_emp.size() == 0) {
            break;
        }
        if (emp.size() == 0) {
            cout << -1 << endl;
            return 0;
        }
        upd(non_emp[0], emp[0]);
    }
    cout << ans.size() << endl;
    for (auto to : ans) {
        cout << to.first + 1 << ' ' << to.second + 1 << endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:72:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |             if (g[i].size() <= j) {
      |                 ~~~~~~~~~~~~^~~~
Main.cpp:128:77: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |             if (pos[type][0].second == 0 && a[i].size() == 1 && a[j].size() == pos[type][1].second + 1) {
      |                                                                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:9: warning: unused variable 'cnt' [-Wunused-variable]
   25 |     int cnt = 0, cur = 0;
      |         ^~~

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