Domino Fundamente XI - 207

#include <bits/stdc++.h>
#define x first
#define y second
#define pi pair < int , int >
#define pb pair < bool , bool >

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector < pi > a(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].y;
    vector < pb > dp(n + 1); // dp[i].x - daca se poate obtine un sir pana la i cu i nerotita
                             // dp[i].y - daca se poate obtine un sir pana la i cu i rotita
    vector < pb > t(n + 1); // t[i].x = 0(1) <=> (i - 1) e nerotita(rotita) (i e NEROTITA)
                            // t[i].y = 0(1) <=> (i - 1) e nerotita(rotita) (i e ROTITA)
    dp[1].x = dp[1].y = true;
    for(int i = 2; i <= n; ++i) {
        if((a[i].x == a[i - 1].y || a[i].x + a[i - 1].y == 6) && dp[i - 1].x)
            dp[i].x = true; // i si (i - 1) nerotite
        if((a[i].x == a[i - 1].x || a[i].x + a[i - 1].x == 6) && dp[i - 1].y) {
            dp[i].x = true; // i nerotita si (i - 1) rotita
            t[i].x = true;
        }
        if((a[i].y == a[i - 1].y || a[i].y + a[i - 1].y == 6) && dp[i - 1].x)
            dp[i].y = true; // i rotita si (i - 1) nerotita
        if((a[i].y == a[i - 1].x || a[i].y + a[i - 1].x == 6) && dp[i - 1].y) {
            dp[i].y = true; // i si (i - 1) rotite
            t[i].y = true;
        }
    }
    if(!dp[n].x && !dp[n].y)
        cout << "Imposibil\n";
    else {
        int i = n, j = dp[n].x ^ 1;
        vector < pi > sol;
        while(i > 0) {
            if(j == 1)
                sol.emplace_back(a[i].x, a[i].y);
            else
                sol.emplace_back(a[i].y, a[i].x);
            if(j == 0)
                j = t[i].x;
            else
                j = t[i].y;
            --i;
        }
        reverse(sol.begin(), sol.end());
        for(auto it : sol)
            cout << it.y << ' ' << it.x << ' ';
    }
}