Cod sursa(job #1070360)

Utilizator Athena99Anghel Anca Athena99 Data 31 decembrie 2013 18:45:12
Problema Taramul Nicaieri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

const int nmax= 100;

struct str {
    int x, y;
} v[nmax+1];

int a[nmax+1], b[nmax+1];
bool u[nmax+1][nmax+1];

bool in_cmp( int x, int y ) {
    if ( v[x].x!=v[y].x ) {
        return v[x].x>v[y].x;
    } else {
        return v[x].y>v[y].y;
    }
}

bool out_cmp( int x, int y ) {
    if ( v[x].y!=v[y].y ) {
        return v[x].y>v[y].y;
    } else {
        return x>y;
    }
}

int main(  ) {
    int n;
    fin>>n;

    int sol= 0;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i].y>>v[i].x;
        a[i]= b[i]= i;
        sol+= v[i].y;
    }

    sort( a+1, a+n+1, out_cmp );
    for ( int i= 1; i<=n; ++i ) {
        sort( b+1, b+n+1, in_cmp );
        for ( int j= 1; v[a[i]].y>0; ++j ) {
            if ( a[i]!=b[j] && u[a[i]][b[j]]==0 && u[b[j]][a[i]]==0 ) {
                u[a[i]][b[j]]= 1;
                --v[a[i]].y, --v[b[j]].x;
            }
        }
    }

    fout<<sol<<"\n";
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=n; ++j ) {
            if ( u[i][j]==1 ) {
                fout<<i<<" "<<j<<"\n";
            }
        }
    }

    return 0;
}