Given an array, convert it to a zigzag pattern.

zigzag.cpp

#include <iostream>
#include <stdlib.h>
#include <vector>

using namespace std;

vector<int> solve(vector<int>& A) {
    int n = A.size();
    
    int a, b, c;
    vector<int> res;
    
    a = max(A[0], A[1]);
    b = min(A[0], A[1]);
    for(int i=0;i<n-2;++i) {
        c = A[i+2];
        if( i & 0x1 ) {
            // take minimum and update
            if( c > b ) {
                // take b
                res.push_back(b);
                b = min(a, c);
                a = max(a, c);
            }
            else {
                // take c
                res.push_back(c);
            }
        }
        else {
            // take maximum and update
            if( c > a ) {
                // take c
                res.push_back(c);
            }
            else {
                res.push_back(a);
                a = max(c, b);
                b = min(c, b);
            }
        }
    }
    if( (n-2) & 0x1 ) {
        res.push_back(b);
        res.push_back(a);
    }
    else {
        res.push_back(a);
        res.push_back(b);
    }
    return res;
}

void verify(const vector<int>& A) {
    for(int i=1;i<A.size()-2;++i) {
        if( i % 2 == 0 ) {
            if( A[i] <= A[i-1] || A[i] <= A[i+1] ) {
                cout << "false" << endl;
                return;
            }
        }
        else {
            if( A[i] >= A[i-1] || A[i] >= A[i+1] ) {
                cout << "false" << endl;
                return;
            }
        }
    }
    cout << "true" << endl;
}

int main()
{
   int n;
   cin >> n;
   
   vector<int> A(n);
   for(int i=0;i<n;++i) {
       A[i] = rand() % 1024;
   }
   
   auto res = solve(A);
   auto pfunc = [](vector<int>& v){
       for(auto x : v ) cout << x << ' ';
       cout << endl;
   };
   verify(res);
   pfunc(A);
   pfunc(res);
   return 0;
}