oj.uz

Submission #832021

# Submission time Handle Problem Language Result Execution time Memory
832021 2023-08-20T20:21:55 Z QwertyPi Parking (CEOI22_parking) C++14
10 / 100
 321 ms 61708 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());
        }
        single.push_back(y);
    }

    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:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for(auto [x, v] : bottoms){
      |              ^
Main.cpp:107:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |     for(auto [x, v] : tops){
      |              ^
Main.cpp:174:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |     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 2 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 1 ms 3412 KB Output is correct
10 Correct 1 ms 3412 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 61708 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

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 Runtime error 5 ms 7252 KB Execution killed with signal 6
2 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 2 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 1 ms 3412 KB Output is correct
10 Correct 1 ms 3412 KB Output is correct
11 Runtime error 321 ms 61708 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -