reorder vector of coordinates into vector of points

reorder.cpp

// x1,x2,…,xn,y1,y2,…,yn will become x1,y1,x2,y2,…,x(n),y(n) in-place

#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
vector<T> expected(vector<T> const& a) {
    vector<T> s(a.size());
    const size_t n = a.size()/2;
    for (size_t i=0; i<n; i++) {
        s[2*i] = a[i];
        s[2*i+1] = a[n+i];
    }
    return s;
}

template <typename T>
void p(vector<T> const& a, vector<T> const& s, size_t k, size_t m) {
    const size_t n = a.size()/2;

    size_t cnt=0;
    for (size_t i=0; i < a.size(); i++) { 
        if (a[i]==s[i]) cnt++;
        cout << a[i] << ( (i==n-1 || i==2*n-1) ? "|" : (a[i+1] == s[i+1] ? "_" : " ")); 
    }; 
    cout << k << ":" << m << " " << cnt << (cnt==a.size() ? " !" : " ") << endl;
}

template <typename T>
vector<T> shuffle(vector<T> a) {

    static bool d = true;
    size_t n = a.size()/2;
    vector<T> s = expected(a);
  
    size_t k=1, m=2*n-2;
    swap(a[k], a[n]);
    swap(a[m], a[n-1]);
    if (n < 4) goto end;
    if (d) p(a, s, k, m);

    k=2; m--;
    swap(a[k], a[n]);
    swap(a[m], a[n-1]);
    if (n < 5) goto end;
    if (d) p(a, s, k, m);

    k=3; m--;
    if (n < 6) {
        swap(a[k], a[m]);
        goto end;
    }
    swap(a[k], a[n+k/2]);
    swap(a[m], a[n-1-k/2]);
    if (d) p(a, s, k, m);
    
    k=4; m--;
    swap(a[k], a[n]);
    swap(a[m], a[n-1]);
    if (n < 7) goto end;
    if (d) p(a, s, k, m);

    k=5; m--;
    if (n == 7) {
        swap(a[k], a[k+1]);
        swap(a[m], a[m-1]);
    }
    else if (m == n+k/2) {
        swap(a[k], a[m]); // actually, also a[n+k/2]
    }
    else {
        swap(a[k], a[n+k/2]);
        swap(a[m], a[n-1-k/2]);
    }
    if (n < 9) goto end;
    if (d) p(a, s, k, m);
    
    k=6; m--;
    swap(a[k], a[n+1]);
    if (m == n+1) goto end;
    swap(a[m], a[n-2]);
    if (d) p(a, s, k, m);

    k=7; m--;
    if (m == n+1) {
        swap(a[k], a[m]);
        goto end;
    }
    if (n == 10) {
        swap(a[k], a[k+1]);
        swap(a[m], a[m-1]);
    }
    else if (n == 11) {
        swap(a[k], a[m]);
    }
    else if (n == 12) {
        swap(a[k], a[m-1]);
        swap(a[m], a[k+1]);
    }
    else if (n == 13) {
        swap(a[k], a[m-2]);
        swap(a[m], a[k+2]);
    }
    if (d) p(a, s, k, m);

    k=8; m--;
    if (n < 13) {
        swap(a[k], a[n]);
        swap(a[m], a[n-1]);
    }
    else {
        swap(a[k], a[n+3]);
        swap(a[m], a[n-4]);
    }
    if (n < 12) goto end;
    if (d) p(a, s, k, m);

    k=9; m--;
    swap(a[k], a[n]);
    swap(a[m], a[n-1]);
    if (n < 12) goto end;
    if (d) p(a, s, k, m);

    k=10; m--;
    swap(a[k], a[n-1]);
    swap(a[m], a[n]);

end:
    if (n != 4 && n != 11 && n != 12) {
        if (d) p(a, s, k, m);
        k++; m--;
        swap(a[k], a[m]);
    }
    p(a, s, k, m);
    return a;
}

template<typename T>
void run(vector<T> a) {
    // for (size_t i=0; i < a.size(); i++) cout << a[i] << " "; cout << endl;
    auto v = shuffle(a);
    // for (size_t i=0; i < a.size(); i++) cout << v[i] << " "; cout << endl << endl;
}

vector<int> gen_i(int n) {
    vector<int> v(2*n);
    for (size_t i=0; i<n; i++) {
        v[i] = 10 + i;
        v[n+i] = 50 + i;
    }
    return v;
}

vector<char> gen(int n) {
    vector<char> v(2*n);
    for (size_t i=0; i<n; i++) {
        v[i] = 'a' + i;
        v[n+i] = 'A' + i;
    }
    return v;
}

int main() {
    // run(vector<int>{11,12,13,21,22,23});
    // run(vector<int>{11,12,13,14,21,22,23,24});
    // run(vector<int>{11,12,13,14,15,21,22,23,24,25});
    // run(vector<int>{11,12,13,14,15,16,21,22,23,24,25,26});
    ///run(vector<int>{11,12,13,14,15,16,17,21,22,23,24,25,26,27});
    // run(vector<int>{11,12,13,14,15,16,17,18,21,22,23,24,25,26,27,28});
    // run(vector<int>{11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29});
    // run(vector<int>{10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29});
    // run(vector<int>{10,11,12,13,14,15,16,17,18,19,30,20,21,22,23,24,25,26,27,28,29,40});
    // run(vector<int>{10,11,12,13,14,15,16,17,18,19,30,31,20,21,22,23,24,25,26,27,28,29,40,41});
    run(gen(12));
    run(gen(13));

    // run(vector<string>{"x1", "x2", "x3", "x4", "x5", "x6", "x7", "x8", "x9", "y1", "y2", "y3", "y4", "y5", "y6", "y7", "y8", "y9"}); // DONE
    // run(vector<string>{"x1", "x2", "x3", "x4", "x5", "x6", "x7", "y1", "y2", "y3", "y4", "y5", "y6", "y7"}); // DONE
    // run(vector<string>{"x1", "x2", "x3", "y1", "y2", "y3"}); // DONE
    // run(vector<string>{"x1", "x2", "x3", "x4", "y1", "y2", "y3", "y4"}); // DONE
}