CDUTSV02 Heist Editorial

PROBLEM LINK: Ordering Cars

AUTHOR: sohit_1212

DIFFICULTY: Medium

PREREQUISITES: Stack

We take the input input in sequence and maintain with us the number of the next car in order.
If the number of car in i/p is same as the required car number , we continue taking the next input or else we check for the required car in the stack, and if found in the stack, we pop it and increment the required car number by 1 and keep looking in the stack.
Else if the car is not found in the stack, we check whether the current car can be put in the stack without disturbing order.

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;
    scanf("%d",&n);
    
    while(n != 0) {

    
        stack<int> s;
        int num = 1;
        int i=0;
        int flag = 0;
        int id = 0;
        for(i=0;i<n;i++) {
            int k = 0;
            scanf("%d",&k);
            
            if(k != num) {
                while(!s.empty() && s.top() == num) {
                    s.pop();
                    num++;
                }
                if(s.empty() || s.top() > k) s.push(k);
                else if(s.top() < k) {
                    flag = -1;
                    id = i;
                }
                
            } else num++;
        }
        while(!s.empty() && s.top() == num) {
            s.pop();
            num++;
        }
        if(flag != -1 && s.empty()) 
            printf("yes\n");
        else printf("no\n");
        
        scanf("%d",&n);   
        
    }
    return 0;
}