103 - Stacking Boxes

// StakingBox.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
// StakingBox.cpp : Defines the entry point for the console application.
//



#include<iostream>
#include<vector>
#include<algorithm>
#include <stdio.h>
using namespace std;

struct Box
{
vector<int> dimentions;
int number;
int numberOfBoxesFit;
int child;
};

bool comparer(Box a, Box b)
{
    vector<int>::iterator itB=b.dimentions.begin();
    for(vector<int>::iterator itA=a.dimentions.begin();itA!=a.dimentions.end();++itA,++itB)
    {
        if(*itA>=*itB)
            return false;
    }
    return true;
}


int main()
{



int k;
int n;

while(scanf("%i%i",&k,&n)!=EOF)
{
vector<Box> boxes;
boxes.clear();
Box box;

for(int i=0;i<k;i++)
{
box.dimentions.clear();
for(int j=0;j<n;j++)
{
int t;
scanf("%d",&t);
box.dimentions.push_back(t);
}
box.number=i+1;
box.numberOfBoxesFit=0;
box.child=-1;
boxes.push_back(box);

}


for (std::vector<Box>::iterator boxIt=boxes.begin(); boxIt!=boxes.end(); ++boxIt)
        std::sort((*boxIt).dimentions.begin(),(*boxIt).dimentions.end());
   
for (int i=0;i<boxes.size();i++)
{
for (int j=0;j<boxes.size();j++)
{
if(i!=j)
{
if(comparer(boxes[i],boxes[j]))
{
Box temp=boxes[i];
boxes[i]=boxes[j];
boxes[j]=temp;
}
}
}
}

int maxVal=0;
int maxBoxIndex=1;
for (int i=0; i<boxes.size(); ++i)
    {      
for (int j=0; j<boxes.size(); ++j)
{
if(i!=j)
{
if(comparer(boxes[j],boxes[i])) //if A is bigger than B
{
if(boxes[i].numberOfBoxesFit<=boxes[j].numberOfBoxesFit)
{
boxes[i].numberOfBoxesFit=boxes[j].numberOfBoxesFit+1;
boxes[i].child=boxes[j].number;
}
if(maxVal<=boxes[i].numberOfBoxesFit)
{
maxVal=boxes[i].numberOfBoxesFit;
maxBoxIndex=boxes[i].number;
}
}
}
}          
    }  

/*for (std::vector<Box>::iterator boxIt=boxes.begin(); boxIt!=boxes.end(); ++boxIt)
    {
        Box b=*boxIt;
cout<<b.number<<". Number of box fits="<<b.numberOfBoxesFit<<" and child "<<b.child<<" :";
        for(vector<int>::iterator it=b.dimentions.begin();it!=b.dimentions.end();++it)
        {
        cout<<*it<<" ";
        }
       
        cout<<endl;
    }*/

   
//cout<<"Max Val:"<<maxVal<<" max box:"<<maxBoxIndex<<endl;
vector<int> result;
int loop=0;
while(1)
{
if(boxes[loop].number==maxBoxIndex)
{
//cout<<boxes[loop].number<<" ";
result.push_back(boxes[loop].number);
if(boxes[loop].child==-1)
break;
maxBoxIndex=boxes[loop].child;
loop=0;

}
else
{
loop=(loop+1)%boxes.size();
}
}

cout<<result.size()<<endl;
for(int i=result.size()-1;i>=0;i--)
{
if(i!=result.size()-1)
cout<<" ";
cout<<result[i];
}

cout<<endl;

}

return 0;
}