Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #include<cstdlib>
- #define MAX_N 3010
- using namespace std;
- int n;
- int ansx[MAX_N], ansy[MAX_N];
- struct rock_tag {
- int x1,x2,y1,y2;
- } rock[MAX_N];
- struct compute_tag {
- int x,y;
- int id;
- bool operator < ( const compute_tag &T ) const {
- return T.y < y;
- }
- } a[MAX_N];
- priority_queue< compute_tag > Q;
- bool cmp( compute_tag p , compute_tag q )
- {
- return p.x < q.x;
- }
- void endprogram()
- {
- printf("NIE\n");
- exit(0);
- }
- void solve(int ans[])
- {
- sort( a+1 , a+1+n , cmp );
- int now = 1;
- for(int c=1;c<=n;c++)
- {
- while( a[now].x <= c and now <= n )
- {
- Q.push( a[now] );
- now ++;
- }
- if( Q.empty() ) endprogram();
- compute_tag z = Q.top();
- Q.pop();
- if( z.y < c ) endprogram();
- ans[ z.id ] = c;
- }
- }
- int main()
- {
- scanf("%d",&n);
- for(int c=1;c<=n;c++) scanf("%d%d%d%d",&rock[c].x1,&rock[c].y1,&rock[c].x2,&rock[c].y2);
- for(int c=1;c<=n;c++) a[c].x = rock[c].x1, a[c].y = rock[c].x2, a[c].id = c;
- solve( ansx );
- for(int c=1;c<=n;c++) a[c].x = rock[c].y1, a[c].y = rock[c].y2, a[c].id = c;
- solve( ansy );
- for(int c=1;c<=n;c++) printf("%d %d\n",ansx[c],ansy[c]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement