Poj Solution 3110

http://poj.org/problem?id=3110

#include <stdio.h>
#include <queue>

using namespace std;

int days[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int getDays( int dd, int mm, int year ) {
    int res = (year-1700)*365 + (year-1700-1)/4 + days[mm-1] + dd;
    if( year > 1800 )
        res--;
    if( year > 1900 )
        res--;
    if( mm > 2 && year % 4 == 0 && ( year % 100 != 0 || year % 400 ==0 ) )
        res ++;
    return res;
}

void toDate( int &dd, int &mm, int &year, int s ) {
    int i, j, t;
    
    year = s/366 + 1700;

    while( getDays( 1, 1, year+1 ) <= s )
        year++;

    for( i=1; i<=12; i++ ) {
        t = days[i]-days[i-1];
        if( i == 2 && year%4 == 0 && ( year%100!=0 || year%400==0 ) )
            t++;
        for( j=1; j<=t; j++ )
            if( getDays( j, i, year ) == s ) {
                dd = j, mm = i;
                return;
            }
    }

    return;
}

struct Exam {
    char w[12];
    int dd, mm, yy;
    int s, t;
}exam[50000];

struct Cmp {
    bool operator()( Exam *a, Exam *b ) const {
        return a->t < b->t;
    }
};

priority_queue< Exam*, vector<Exam*>, Cmp > q;

bool cmp( const Exam &a, const Exam &b ) {
    return a.s>b.s;
}

int main( ) {
    int i, n, ans;
    bool key = true;
    for( i=1; i<=12; i++ )
        days[i] += days[i-1];

    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%s%d.%d.%d%d", &exam[i].w, &exam[i].dd, &exam[i].mm, &exam[i].yy, &exam[i].t );
        exam[i].s = getDays( exam[i].dd, exam[i].mm, exam[i].yy );
        exam[i].t = exam[i].s-exam[i].t;
    }

    sort( exam, exam+n, cmp );
    
    ans = 10000000;
    for( i=0; i<=n && key; i++ ) {
        while( !q.empty() && ( i== n || ans > exam[i].s ) ) {
            if( ans < q.top()->t ) {
                key = false;
                break;
            }
            ans--;
            q.pop();
        }
        if( i < n ) {
            q.push( &exam[i] );
            ans = exam[i].s-1;
        }
    }

    if( !key )
        printf( "Impossiblen" );
    else {
        int a, b, c;
        toDate( a, b, c, ans+1 );
        printf( "%02d.%02d.%04dn", a, b, c );
    }
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *