oj.uz

Submission #634767

# Submission time Handle Problem Language Result Execution time Memory
634767 2022-08-24T21:37:55 Z Ooops_sorry Parking (CEOI22_parking) C++14
10 / 100
 2000 ms 104248 KB 
#define _GLIBCXX_DEBUG
#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;
    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) {
            num[cur] = a[i][0];
            val[i][0] = cur++;
            pos[a[i][0]].pb({i, 0});
        }
        if (a[i].size() > 1) {
            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;
                while (q.size() > 0) {
                    int v = q.back();
                    q.pop_back();
                    for (auto to : g[v]) {
                        if (!used[to]) {
                            used[to] = 1;
                            q.pb(to);
                            if (is_top[v] && is_top[to]) {
                                ord.pb(num[v]);
                            }
                        }
                    }
                }
            }
        }
    }
    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;
        bool good = 1;
        for (int i = 0; i < m; i++) {
            if (a[i].size() == 0) continue;
            good &= a[i].size() == 2 && a[i][0] == a[i][1];
        }
        if (good) break;
        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();
            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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 104248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1292 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 14 ms 1108 KB Output is correct
4 Correct 7 ms 908 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 16 ms 1236 KB Output is correct
7 Correct 3 ms 1332 KB Output is correct
8 Correct 16 ms 1332 KB Output is correct
9 Correct 16 ms 1364 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 19 ms 1364 KB Output is correct
12 Correct 18 ms 1348 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 2 ms 1364 KB Output is correct
16 Incorrect 3 ms 1364 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Execution timed out 2093 ms 104248 KB Time limit exceeded
12 Halted 0 ms 0 KB -