oj.uz

Submission #832016

# Submission time Handle Problem Language Result Execution time Memory
832016 2023-08-20T20:14:18 Z QwertyPi Parking (CEOI22_parking) C++14
20 / 100
 603 ms 38708 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() == 0) bottoms[S[y].top()].erase(find(all(bottoms[S[y].top()]), x));
    tops[S[y].top()].erase(find(all(tops[S[y].top()]), x));
    tops[S[y].top()].push_back(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);
    }


    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:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [x, v] : bottoms){
      |              ^
Main.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for(auto [x, v] : tops){
      |              ^
Main.cpp:170:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  170 |     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 1 ms 3412 KB Output is correct
3 Correct 1 ms 3412 KB Output is correct
4 Correct 1 ms 3412 KB Output is correct
5 Correct 1 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 2 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 510 ms 31928 KB Output is correct
2 Correct 603 ms 38708 KB Output is correct
3 Correct 310 ms 24764 KB Output is correct
4 Correct 307 ms 22972 KB Output is correct
5 Correct 577 ms 37972 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 3 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 4 ms 3668 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 5 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 5 ms 3668 KB Output is correct
9 Correct 5 ms 3668 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 4 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 3540 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct
16 Incorrect 2 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 1 ms 3412 KB Output is correct
3 Correct 1 ms 3412 KB Output is correct
4 Correct 1 ms 3412 KB Output is correct
5 Correct 1 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 2 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 510 ms 31928 KB Output is correct
12 Correct 603 ms 38708 KB Output is correct
13 Correct 310 ms 24764 KB Output is correct
14 Correct 307 ms 22972 KB Output is correct
15 Correct 577 ms 37972 KB Output is correct
16 Incorrect 3 ms 3540 KB Output isn't correct
17 Halted 0 ms 0 KB -