HDU 5360 Hiking

Problem Description

n soda conveniently labeled by 

1,2,…,n. beta, their best friends, wants to invite some soda to go hiking. The 

i-th soda will go hiking if the total number of soda that go hiking except him is no less than 

li and no larger than 

ri. beta will follow the rules below to invite soda one by one:

1. he selects a soda not invited before;

2. he tells soda the number of soda who agree to go hiking by now;

3. soda will agree or disagree according to the number he hears.

Note: beta will always tell the truth and soda will agree if and only if the number he hears is no less than 

li and no larger than 

ri, otherwise he will disagree. Once soda agrees to go hiking he will not regret even if the final total number fails to meet some soda's will.

Help beta design an invitation order that the number of soda who agree to go hiking is maximum.

Input

T, indicating the number of test cases. For each test case:

The first contains an integer 

n 

(1≤n≤105), the number of soda. The second line constains 

n integers 

l1,l2,…,ln. The third line constains 

n integers 

r1,r2,…,rn. 

(0≤li≤ri≤n)

It is guaranteed that the total number of soda in the input doesn't exceed 1000000. The number of test cases in the input doesn't exceed 600.

Output

1,2,…,n denoting the invitation order. If there are multiple solutions, print any of them.

Sample Input

4
8
4 1 3 2 2 1 0 3
5 3 6 4 2 1 7 6
8
3 3 2 0 5 0 3 6
4 5 2 7 7 6 7 6
8
2 2 3 3 3 0 0 2
7 4 3 6 3 2 2 5
8
5 6 5 3 3 1 2 4
6 7 7 6 5 4 3 5      

Sample Output

7
1 7 6 5 2 4 3 8
8
4 6 3 1 2 5 8 7
7
3 6 7 1 5 2 8 4
0
1 2 3 4 5 6 7 8      

#include<cstdio>
#include<cmath>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=100005;
int T,n,m,l[maxn],r[maxn],ans[maxn],tot,f[maxn];

struct lr
{
    int l,r,id;
    lr(int l,int r,int id):l(l),r(r),id(id){};
    bool operator <(const lr& a)const
    {
        if (r==a.r) return l>a.l;
        return r>a.r;
    }
};

vector<lr> p[maxn];

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);    tot=0;
        for (int i=1;i<=n;i++) scanf("%d",&l[i]);
        for (int i=1;i<=n;i++) scanf("%d",&r[i]);
        for (int i=0;i<=n;i++) p[i].clear();
        for (int i=1;i<=n;i++) p[l[i]].push_back(lr(l[i],r[i],i));
        priority_queue<lr> que;
        for (int i=0;i<=n;)
        {
            for (int j=0;j<p[i].size();j++) que.push(lr(p[i][j]));
            while (!que.empty()&&que.top().r<i) que.pop();
            if (!que.empty()) {ans[tot++]=que.top().id; que.pop(); i++;}
            else break;
        }
        printf("%d\n",tot);
        if (tot) 
        {
            memset(f,0,sizeof(f));
            printf("%d",ans[0]);
            for (int i=1;i<tot;i++) printf(" %d",ans[i]);
            for (int i=0;i<tot;i++) f[ans[i]]=1;
            for (int i=1;i<=n;i++) if (!f[i]) printf(" %d",i);
        }
        else for (int i=1;i<=n;i++) 
        {
            if (i>1) printf(" ");
            printf("%d",i);
        }
        printf("\n");
    }
    return 0;
}