Time Lapse :35min 39sec

4256.cpp

#include <iostream>
#define pc(x) putchar_unlocked(x)
#define gc() getchar_unlocked()
using namespace std;
struct Node{
    Node* l;
    Node* r;
    int val;
};
int tc, n;
int preOrder[1000];
int inOrder[1000];
int fRI(){
    int N = gc(), ret = 0, flag = 1;
    for(;N<'0'||N>'9';N=gc())
        if(N=='-'){
            flag=-1; N=gc(); break;
        }
    do{
        ret = (ret<<3) + (ret<<1) + (N & 0b1111);    N=gc();
    }while('0'<=N&&N<='9');
    return ret*flag;
}
inline void fWI (int n){
    int N = n, rev, count = 0;
    rev = N;
    while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}  //store reverse of N in rev
    while (rev != 0) { pc(rev % 10 | 0b110000); rev /= 10;}
    while (count--) pc('0');
    pc(' ');
}
Node* initNode() {
    Node* node = new Node();
    node-> val = -1;
    node->l = node->r = nullptr;
    return node;
}
Node* buildNode(Node* node, int pStart, int pEnd, int iStart, int iEnd) {
    if(pStart > pEnd || iStart > iEnd) return nullptr;
    node = initNode();
    node->val = preOrder[pStart];
    if(pStart == pEnd) return node;
    int inOderPos;
    for(inOderPos = iStart; inOderPos <= iEnd; inOderPos++)
        if(inOrder[inOderPos] == preOrder[pStart])
            break;
    node -> l = buildNode(node->l, pStart + 1, pStart + inOderPos - iStart, iStart, inOderPos-1);
    node -> r = buildNode(node->r, pStart + inOderPos - iStart + 1, pEnd, inOderPos+1, iEnd);
    return node;
}
void postOrder(Node* node) {
    if(node->l != nullptr) postOrder(node->l);
    if(node->r != nullptr) postOrder(node->r);
    fWI(node->val);
}
int main(){
    tc = fRI();
    while(tc--) {
        n = fRI();
        for(int i = 0; i < n; i++)
            preOrder[i] = fRI();
        for(int i = 0; i < n; i++)
            inOrder[i] = fRI();
        postOrder(buildNode(nullptr, 0, n - 1, 0, n - 1));
        pc('\n');
    }
}