UVa 101 - The Blocks Problem

101.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

typedef stack<int> pila;
typedef vector<pila> vpila;

bool find(pila &p, int val) {
    if(p.empty()) return false;
    if(p.top() == val ) return true;

    int el = p.top(); p.pop();
    bool c = find( p, val );

    p.push( el );
    return c;
}

int vector_find(vpila &A, int val) {
    for(int i=0; i<A.size(); i++)
        if(find( A[i], val )) return i;
    return -1;
}

void onto(vpila &A, int idx, int val) {
    if(A[idx].top() == val) return;

    int p = A[idx].top();
    A[ p ].push( p );
    A[idx].pop();

    onto(A, idx, val);

}

void til(vpila &A, int idx, int jdx, int val) {
    if(A[idx].top() == val) {
        A[jdx].push( A[idx].top() );
        A[idx].pop();
        return;
    }

    int v = A[idx].top(); A[idx].pop();
    til(A, idx, jdx, val);
    A[jdx].push( v );
}

void restack(vpila &A, int idx, int jdx) {
    A[jdx].push(A[idx].top());
    A[idx].pop();
}

vi to_vi(pila T) {
    vi A;
    while(!T.empty()) {
        A.PB(T.top());
        T.pop();
    }
    reverse(A.begin(), A.end());
    return A;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, b, i, j;
    string on, der;

    cin >> n;

    vpila A(n);
    for(int i=0; i<n; i++) A[i].push(i);

    while(cin >> on && on != "exit") {
        cin >> a >> der >> b;
        if(a == b) continue;

        i = vector_find(A, a);
        j = vector_find(A, b);

        if(i == j) continue;

        if(on == "move") {
            if(der == "onto") {
                // Returning to initial positions
                onto(A, i, a);
                onto(A, j, b);
                restack(A, i, j);

            } else {
                onto(A, i, a);
                restack(A, i, j);
            }
        } else {
            if(der == "onto") {
                onto(A, j, b);
                til(A, i, j, a);
            } else {
                til(A, i, j, a);
            }
        }

    }

    for(int i=0; i<n; i++) {
        cout << i << ":";
        vi N = to_vi(A[i]);
        for(int i : N) cout << " " << i; cout << endl;
    }

    return 0;
}