BUS - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

CAKEWALK

PROBLEM:

There is an empty bus with M seats. There are N passengers. Given a list of length Q, the order in which the passengers entered and exited the bus. Determine if the list is consistent (passengers leave only after they board the bus; the number of passengers don’t exceed M at any given time).

EXPLANATION:

Maintain an array that holds the boarding status of the N passengers (1 if the passenger is on the bus and 0 otherwise) . All values are initially 0. Also maintain a variable cnt, representing the number of passengers on the bus. cnt is initially 0.

Now, iterate over the list. For each + move, verify if the boarding status of the passenger is 0 (otherwise the list is inconsistent). Similarly, for each - move, verify if the boarding status of the passenger is 1.

Lastly, update the values of the boarding status and cnt (add 1 for + move, subtract 1 for - move) and verify if cnt \le M.

If at any time, the verification doesn’t hold, the list is inconsistent. Else it is consistent.

TIME COMPLEXITY:

For each test case, Q operations are done (one for each entry in the list).

Thus, the time complexity is O(Q) per test case.

SOLUTIONS:

Editorialist’s solution can be found here.


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

can any one pls say why i am getting WA for this code

#include<bits/stdc++.h>
using namespace std;

void solve(){
long n,m,q,count=0,flag=0; cin>>n>>m>>q; vectorv(3n);
for(long i=0;i<3
n;i++){
cin>>v[i];

if(v[i]=='+') count++;
    
   else if(count>m){
        
        cout<<"Inconsistent\n";
        return;
        
    }
 else if(v[i]=='-'){
      count--;
      auto it = find(v.begin(),v.end(),v[i+1]);
    cout<<*it;
     for(int i=0;i<v[i+1];i++)if(v[i]==*it){flag=1; break;}
     
          
           if(flag==0){
            cout<<"Inconsistent\n";
        return;
           }
       }
      
    }

   if(count<=m)cout<<"Consistent\n";

}
int main(){
long tc; cin>>tc;
while(tc–>0)solve();
return 0;
}