fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<list>
  5. #include<deque>
  6. #include<map>
  7. #include<set>
  8. #include<iterator>
  9. #include<climits>
  10. #include<cmath>
  11.  
  12. typedef long long int ll;
  13. typedef unsigned long long int ull;
  14.  
  15. using namespace std;
  16.  
  17. void solve() {
  18.     int n,m,k,num;
  19.     cin>>n>>m;
  20.     deque<deque<int>> cylinders;
  21.     //creates 2d deque for storing ball numbers present in each cylinder.
  22.     for(int i=0;i<m;i++){
  23.         deque<int> ithCyclinder;
  24.         cin>>k;
  25.         for(int i=0;i<k;i++) {
  26.             cin>>num;
  27.             ithCyclinder.push_back(num);
  28.         }
  29.         cylinders.push_back(ithCyclinder);
  30.     }
  31.     /*
  32.         cout<<"\n----\n";
  33.         for(int i=0;i<cylinders.size();i++) {
  34.             for(int j=0;j<cylinders[i].size();j++) {
  35.                 cout<<cylinders[i][j]<<" ";
  36.             }
  37.             cout<<"\n";
  38.         }
  39.     */
  40.  
  41.     // maps ballNumber to the cylinder numbers if the ballNumber is present at the front of the cylinder. 
  42.     // for example: if ballNumber 1 is present at the front of cylinder numbers 4 and 5, it stores 1->[4,5]
  43.     map<int,vector<int>> mapping; 
  44.  
  45.     // maintains the list of ball numbers with the same color which are present at the front of cylinder in the current iteration.
  46.     deque<int>sameBallsList;
  47.     for(int i=0;i<m;i++){
  48.         //maps the ballNumber present at the front of cylinder i to the cylinder number i. 
  49.         //for example: if 4 is present at the front of 2nd cylinder, it maps 4->[2]
  50.         mapping[cylinders[i][0]].push_back(i);
  51.  
  52.         //checks if after mapping the current ballNumber to the cylinder i, is the 
  53.         //ballNumber already present at the front of some other cylinder (let's say cylinder j)
  54.         // if it is already present for some cylinder j, it adds the current ballNumber to sameBallsList.
  55.         if(mapping[cylinders[i][0]].size()==2) sameBallsList.push_back(cylinders[i][0]);
  56.     }
  57.     int count=0;
  58.  
  59.     //if the sameBallsList contains an element, it means we have 2 balls of the same colour at the front of their 
  60.     //respecitve cylinders. so we pop the balls out from the front of the cylinders, and check if there are new
  61.     // pairs of balls in front of the cylinder. if there are, we append the ballNumber to the sameBallsList vector.
  62.     while(sameBallsList.size()){
  63.     /*
  64.         for(int i=0;i<sameBallsList.size();i++) cout<<sameBallsList[i]<<" ";
  65.         cout<<endl;
  66.     */
  67.  
  68.         //get the ballNumber present at the front of sameBallsList and then pop sameBallsList
  69.         int BallNumber=sameBallsList.front();
  70.         sameBallsList.pop_front();
  71.  
  72.         // get indices of the cylinders at the front of which the current ballNumber is present. for example: if ballNumber 3 is present at the front of the 
  73.         // cylinders 1 and 4, cylinder1=1 and cylinder2=4. then pop both the cylinders.
  74.         int cylinder1= mapping[BallNumber][0];
  75.         int cylinder2= mapping[BallNumber][1];
  76.  
  77.         cylinders[cylinder1].pop_front();
  78.         cylinders[cylinder2].pop_front();
  79.  
  80.         //get the balls present at the front of both the cylinders.
  81.         int ball1 = 0,ball2 = 0;
  82.         if(!cylinders[cylinder1].empty())
  83.             ball1= cylinders[cylinder1].front();
  84.         if(!cylinders[cylinder2].empty())
  85.             ball2= cylinders[cylinder2].front();
  86.  
  87.         //if the ball popped is 0, it means that the cylinder was empty, since from the test case constraints, we
  88.         // can infer that their will be no ball of color 0.
  89.         if(ball1!=0)
  90.             mapping[ball1].push_back(cylinder1);
  91.         if(ball2!=0)
  92.             mapping[ball2].push_back(cylinder2);
  93.  
  94.         // if both balls are same, we need to append the ballNumber to the sameBallsList just once.
  95.         if (ball1==ball2&&ball1&&ball2) {
  96.             sameBallsList.push_back(ball2);
  97.         }
  98.         else {
  99.             if(ball1&&mapping[ball1].size()==2) sameBallsList.push_back(ball1);
  100.             if(ball2&&mapping[ball2].size()==2) sameBallsList.push_back(ball2);
  101.         }
  102.         count++;
  103.     }
  104.     //cout<<count<<endl;
  105.     //if all the balls are popped, it means there is a way to remove all balls from all cylinders and hence empty all m cylinders.
  106.     if(count==n) cout<<"Yes";
  107.     else cout<<"No";
  108.  
  109. }
  110.  
  111. int main() {
  112.     int t=1;
  113.     //cin>>t;
  114.     while(t--){
  115.         solve();
  116.         cout<<"\n";
  117.     }
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/bmq1L6
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!