10895 - Matrix Transpose UVA.cpp

/**
La idea principal es representar la matriz como una lista de ayacencia.
Para hacer el transpuesta esun proceso ad-hoc

**/


#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
using namespace std;

typedef pair<int,int> ii;//(valor,posicion)
typedef vector<ii> vii;

 struct compare
 {
   bool operator()(const int& l, const int& r)
   {
       return l > r;
   }
 };
int r,c; //fila y columnas
vector <vii> G;//matriz M
vector <vii> G2;//la transpuesta de la matriz M

int main(){
    while(scanf("%d %d",&r,&c) !=EOF){

        //incializamos ambos vectores
        G.assign(r,vii());
        G2.assign(c,vii());

        for(int i=0;i<r;i++){
            int n,aux;
            scanf("%d",&n);
            while(n--){
                scanf("%d",&aux);
                G[i].push_back(ii(0,aux));
            }
            for(int e=0;e<G[i].size();e++){
                scanf("%d",&aux);
                G[i][e].first=aux;
            }
        }
        int x=1;


        while(x<=c){
            for(int i=0;i<r;i++){
                if(G[i].size()>0 && G[i][0].second == x){
                    G2[x-1].push_back(ii(G[i][0].first,i+1));
                    G[i].erase(G[i].begin());
                }
            }


            x++;
        }



        printf("%d %d\n",c,r);
        for(int i=0;i<c;i++){
            printf("%d",G2[i].size());
            for(int e=0;e<G2[i].size();e++){
                printf(" %d",G2[i][e].second);
            }
            printf("\n");
            for(int e=0;e<G2[i].size();e++){
                if(e!=0)
                    printf(" ");
                printf("%d",G2[i][e].first);
            }
            printf("\n");
        }


    }
    return 0;

}