oj.uz

Submission #832011

# Submission time Handle Problem Language Result Execution time Memory
832011 2023-08-20T20:06:38 Z QwertyPi Parking (CEOI22_parking) C++14
20 / 100
 593 ms 38652 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){
        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();
    }
    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:164:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  164 |     for(auto [x, y] : ans){
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 2 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 2 ms 3460 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 458 ms 31908 KB Output is correct
2 Correct 588 ms 38652 KB Output is correct
3 Correct 312 ms 24772 KB Output is correct
4 Correct 295 ms 23144 KB Output is correct
5 Correct 593 ms 37940 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 4 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 3700 KB Output is correct
7 Correct 2 ms 3568 KB Output is correct
8 Correct 4 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 3796 KB Output is correct
12 Correct 4 ms 3668 KB Output is correct
13 Correct 2 ms 3572 KB Output is correct
14 Correct 2 ms 3540 KB Output is correct
15 Correct 2 ms 3568 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 2 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 1 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 2 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 2 ms 3460 KB Output is correct
10 Correct 1 ms 3412 KB Output is correct
11 Correct 458 ms 31908 KB Output is correct
12 Correct 588 ms 38652 KB Output is correct
13 Correct 312 ms 24772 KB Output is correct
14 Correct 295 ms 23144 KB Output is correct
15 Correct 593 ms 37940 KB Output is correct
16 Incorrect 2 ms 3540 KB Output isn't correct
17 Halted 0 ms 0 KB -