oj.uz

Submission #832013

# Submission time Handle Problem Language Result Execution time Memory
832013 2023-08-20T20:10:15 Z QwertyPi Parking (CEOI22_parking) C++14
20 / 100
 593 ms 38640 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

const int MAXN = 2e5 + 11;

map<int, vector<int>> pos;
struct slot{
    int id, a[2], cnt = 0;
    int count(){ cnt = 0; if(a[0] != 0) cnt++; if(a[1] != 0) cnt++; return cnt; }
    int top(){ if(cnt == 0) return 0; return a[cnt - 1]; }
    void remove(){ assert(cnt != 0); pos[a[cnt - 1]].erase(find(pos[a[cnt - 1]].begin(), pos[a[cnt - 1]].end(), id)); a[--cnt] = 0; }
    void add(int x, bool init = false){ assert(cnt != 2); assert(init || !(cnt == 1 && a[0] != x)); pos[x].push_back(id); a[cnt++] = x; }
    bool same(){ return a[0] == a[1] && a[0] != 0; }
    int other(int x){ assert(count() == 2); return a[0] + a[1] - x; }
} S[MAXN];

void failure(){
    cout << -1 << endl;
    exit(0);
}

int n, m; 
bool done[MAXN];

vector<pair<int, int>> ans;

map<int, vector<int>> tops, bottoms;
vector<int> immediate, single, both_top, empty_space;

void move(int x, int y){
    // printf("move: %d => %d\n", x, y);
    assert(1 <= x && x <= m && 1 <= y && y <= m && x != y);
    S[y].add(S[x].top()); S[x].remove();
    ans.push_back({x, y});

    if(S[x].count()){
        tops[S[x].top()].push_back(x);
        bottoms[S[x].top()].push_back(x);
        if(tops[S[x].top()].size() == 2){
            immediate.push_back(S[x].top());
        }
    }else{
        empty_space.push_back(x);
    }

    tops[S[y].top()].erase(find(all(tops[S[y].top()]), x));
    tops[S[y].top()].push_back(y);

    if(S[y].count() == 1){
        bottoms[S[y].top()].push_back(y);
        if(tops[S[y].top()].size() == 2){
            immediate.push_back(S[y].top());
        }
    }

    if(S[y].same()){
        done[S[y].top()] = true;
    }
}

void print(){
    for(int i = 1; i >= 0; i--){
        for(int j = 1; j <= m; j++){
            cout << S[j].a[i] << " \n"[j == m];
        }
    }
}

int32_t main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        S[i].id = i;
        if(x != 0) S[i].add(x);
        if(y != 0) S[i].add(y, true);
    }

    for(int i = 1; i <= m; i++){
        if(S[i].same()){
            done[S[i].top()] = true;
            continue;
        }
        if(S[i].count() == 0){
            empty_space.push_back(i);
        }else{
            tops[S[i].top()].push_back(i);
            if(S[i].count() == 1){
                bottoms[S[i].top()].push_back(i);
                single.push_back(S[i].top());
            }
        }
    }

    for(auto [x, v] : bottoms){
        if(tops[x].size() == 2){
            immediate.push_back(x);
        }
    }

    for(auto [x, v] : tops){
        if(v.size() == 2){
            both_top.push_back(x);
        }
    }

    int not_done = 1;
    while(not_done <= n){
        while(empty_space.size() && S[empty_space.back()].count() != 0) empty_space.pop_back();
        if(immediate.size()){
            int x = immediate.back(); immediate.pop_back();
            if(done[x]) continue;
            vector<int> top = tops[x];
            vector<int> bottom = bottoms[x];
            int from = top[0] == bottom[0] ? top[1] : top[0];
            int to = bottom[0];
            move(from, to);
            continue;
        }
        if(empty_space.size() && single.size()){
            int x = single.back(); single.pop_back();
            if(done[x]) continue;
            vector<int> st;

            vector<int> p = pos[x];
            assert(p.size() == 2);
            if(S[p[1]].count() == 1) swap(p[0], p[1]);
            assert(S[p[1]].count() == 2);
            st.push_back(S[p[1]].other(x));
            while(true){
                int y = st.back();
                vector<int> p2 = pos[y];
                assert(p2.size() == 2);
                if(S[p2[0]].top() == y && S[p2[1]].top() == y) break;
                if(S[p2[0]].top() == y) swap(p2[0], p2[1]);
                st.push_back(S[p2[0]].top());
            }
            int e = empty_space.back(); empty_space.pop_back();
            vector<int> p3 = pos[st.back()];
            move(p3[0], e);
            move(p3[1], e);
            continue;
        }
        if(empty_space.size() && both_top.size()){
            int x = both_top.back(); both_top.pop_back();
            if(done[x]) continue;
            int e = empty_space.back(); empty_space.pop_back();
            vector<int> p3 = pos[x];
            move(p3[0], e);
            move(p3[1], e);
            continue;
        }
        while(done[not_done] && not_done <= n) not_done++;
        if(empty_space.size() && not_done <= n){
            int x = not_done;
            int e = empty_space.back(); empty_space.pop_back();
            vector<int> p = pos[x];
            if(S[p[0]].top() != x) swap(p[0], p[1]);
            move(p[0], e);
            continue;
        }
        if(not_done <= n) failure();
    }
#ifdef LOCAL
    print();
#endif
    cout << ans.size() << endl;
    for(auto [x, y] : ans){
        cout << x << ' ' << y << endl;
    }
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |     for(auto [x, v] : bottoms){
      |              ^
Main.cpp:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for(auto [x, v] : tops){
      |              ^
Main.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |     for(auto [x, y] : ans){
      |              ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 31944 KB Output is correct
2 Correct 593 ms 38640 KB Output is correct
3 Correct 338 ms 24756 KB Output is correct
4 Correct 283 ms 22972 KB Output is correct
5 Correct 579 ms 38024 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3540 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 3540 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 5 ms 3668 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 4 ms 3668 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 4 ms 3668 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 6 ms 3668 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 5 ms 3668 KB Output is correct
12 Correct 4 ms 3668 KB Output is correct
13 Correct 2 ms 3540 KB Output is correct
14 Correct 2 ms 3604 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct
16 Incorrect 3 ms 3540 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 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 1 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 1 ms 3412 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 1 ms 3412 KB Output is correct
11 Correct 489 ms 31944 KB Output is correct
12 Correct 593 ms 38640 KB Output is correct
13 Correct 338 ms 24756 KB Output is correct
14 Correct 283 ms 22972 KB Output is correct
15 Correct 579 ms 38024 KB Output is correct
16 Incorrect 2 ms 3540 KB Output isn't correct
17 Halted 0 ms 0 KB -