 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;
}