Code: Select all
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<string>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>
#define ALL(data) data.begin(),data.end()
#define VI vector<int>
#define VVI vector<vector<int> >
#define VS vector<string>
#define VSI vector<vector<string> >
#define PB push_back
using namespace std;
struct node{
int index;
int l;
int r;
} ;
struct nd{
int index;
int x;
} ;
int n;
bool f;
bool operator<(const node& a ,const node& b){
if(a.r==b.r){
return a.l<b.l;
}
return a.r<b.r;
}
bool operator<(const nd& a ,const nd& b){
return a.index<b.index;
}
vector<nd> fun(vector<node> v){
vector<nd> ret(n);
sort(v.begin(),v.begin()+n);
for(int i=0;i<n;i++){
if(v[i].l-1>i || v[i].r-1<i) {
f = true;
return ret;
}
ret[i].x = i+1;
ret[i].index = v[i].index;
}
return ret;
}
int main(){
vector<node> x(5001),y(5001);
vector<nd> vX , vY;
scanf("%d",&n);
while(n){
for(int i=0;i<n;i++){
x[i].index = i;
y[i].index = i;
scanf("%d%d%d%d",&x[i].l,&y[i].l,&x[i].r,&y[i].r);
}
f = false;
vX = fun(x);
if(f){
printf("IMPOSSIBLE\n");
}
else{
vY = fun(y);
if(f){
printf("IMPOSSIBLE\n");
}
else{
sort(vX.begin(),vX.begin()+n);
sort(vY.begin(),vY.begin()+n);
for(int i=0;i<n;i++){
printf("%i %i\n",vX[i].x,vY[i].x);
}
}
}
scanf("%d",&n);
}
return 0;
}
Nice! Heap will work for N*log(N)subbu wrote:You can do it in O(NlogN).
You can solve for the columns and rows independently, as you mentioned.
For assigning the rooks to different columns, here is a hint, in the form of questions
You can ignore 1 below, if you know an O(N^2) solution aleady.
1) Let x = how many rooks can be assigned to the first column.
1a) What if x = 0?
1b) What if x = 1 ?
1c) What if x > 1 ? Which rook among those that match, would you choose, so that if there is a solution, there is a solution with this rook chosen.
After answering the above, you will probably have an idea of the solution, and a way to do it in O(N^2).
For getting to O(NlogN),
Choosing the "best rook" for the current column C depends on
1) rooks assigned so far
2) rooks whose range contains the current column.
3) Among the rooks whose range contains C, which one has the "least" range to the right of the current column. Can the right end point of the "range" of these rooks help ?
I think your code fails this:vinay wrote:can anyone give some test cases atleast...
i think its some boundary conditions...
Code: Select all
3
1 1 3 3
1 1 3 3
2 2 2 2
Code: Select all
1 1
3 3
2 2
there is an O(n) solution !!!