# 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.