oj.uz

Submission #832023

# Submission time Handle Problem Language Result Execution time Memory
832023 2023-08-20T20:25:06 Z QwertyPi Parking (CEOI22_parking) C++14
20 / 100
 590 ms 39008 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){
#ifdef LOCAL
    printf("move: %d => %d\n", x, y);
#endif
    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());
        }
        single.push_back(S[y].top());
    }

    if(tops[S[y].top()].size() == 2){
        both_top.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:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for(auto [x, v] : bottoms){
      |              ^
Main.cpp:109:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     for(auto [x, v] : tops){
      |              ^
Main.cpp:176:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |     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 2 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 2 ms 3412 KB Output is correct
7 Correct 2 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 497 ms 32384 KB Output is correct
2 Correct 590 ms 39008 KB Output is correct
3 Correct 351 ms 25216 KB Output is correct
4 Correct 322 ms 23108 KB Output is correct
5 Correct 582 ms 38380 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 4 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 4 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 5 ms 3668 KB Output is correct
12 Correct 5 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 3584 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 2 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 2 ms 3412 KB Output is correct
7 Correct 2 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 497 ms 32384 KB Output is correct
12 Correct 590 ms 39008 KB Output is correct
13 Correct 351 ms 25216 KB Output is correct
14 Correct 322 ms 23108 KB Output is correct
15 Correct 582 ms 38380 KB Output is correct
16 Incorrect 2 ms 3540 KB Output isn't correct
17 Halted 0 ms 0 KB -