https://codeforces.com/gym/102511/problem/A
题目大意：
给两个二元组 分别为 a1.first -an.first
a1.second-an.second
b1.first-bn.first
b1.seocnd-bn.second
现在对两个二元组进行排序，使得两个二元组分别以第一关键字单调不减。同时，对于每一个i ai.second > bi.second 始终得到满足 。请输出最终的两个序列的排列情况 （以初始下标输出）
思路：
如果一个区间内某个二元组序列的第一关键字一样，我们称之为可变区间（这个区间内的元素随意排列不影响第一个条件的成立）
从1-n枚举下标：
1.对于一个下标，若a和b在当前位置均不属于可变区间，则直接固定当前位置的答案，并判断是否可行。
2.对于一个下标，若a可变，b不可变，则固定b，在a中当前下标所属的可变区间集合中找到第一个大于当前位置的b元素的元素，将其从集合中移除并放在当前位置，这个a的可变区间大小-1；
3.同理，若b可变，a不可变，则在b中找到第一个小于当前固定的a元素的元素将其从b中移除。
4.对于一个下标，若a和b中当前下标均属于可变区间，若当前位置的a中的第二关键字所在可变区间的元素个数小于b中第二关键字。则按照从小到大的顺序固定元素数小的可变区间，问题变为一个属于可变区间而另一个不属于的情况。
代码
#include<bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define rush! ios::sync_with_stdio(false);cin.tie(0); const int inf = 0x3f3f3f3f; const long long linf = 0x3f3f3f3f3f3f3f3f; const int N=200005; const int mod=1e9+7; typedef long long ll; ll f[N],invf[N]; ll fpow(ll a,ll k){ ll res=1; while(k){ if(k&1) res=(res*a)%mod; k>>=1; a=a*a%mod; //cout<<1<<endl; } return res; } void init(int n){ f[0]=1; for(int i=1;i<=n;++i){ f[i]=f[i-1]*i%mod; } invf[n]=fpow(f[n],mod-2); for(int i=n-1;i>=0;--i){ invf[i]=invf[i+1]*(i+1)%mod; } } ll C(int n,int k){ if(k<0 || k>n) return 0; return f[n]*invf[k]%mod*invf[n-k]%mod; } ll ban[500005]; struct st{ int first; int second; int ind; }a[500005],b[500005]; struct stt{ int l,r; }cnta[500005],cntb[500005]; int va[500005]; int vb[500005]; bool cmp(const st &x,const st &y){ if(x.first==y.first){ return x.second<y.second; } return x.first<y.first; } ll ans1[500005]; ll ans2[500005]; set<pair<int ,int > >s1[500005],s2[500005]; void solve(){ ll n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].first; a[i].ind=i; } for(int i=1;i<=n;i++){ cin>>a[i].second; } for(int i=1;i<=n;i++){ cin>>b[i].first; b[i].ind=i; } for(int i=1;i<=n;i++){ cin>>b[i].second; } sort(a+1,a+1+n,cmp); sort(b+1,b+1+n,cmp); for(int i=1;i<=n;i++){ if(a[i].first==a[i-1].first){ va[i]=va[i-1]=1; if(cnta[i-1].l){ cnta[i].l=cnta[i-1].l; } else{ cnta[i-1].l=i-1; cnta[i].l=i-1; } } if(b[i].first==b[i-1].first){ if(cntb[i-1].l){ cntb[i].l=cntb[i-1].l; } else{ cntb[i-1].l=i-1; cntb[i].l=i-1; } vb[i]=vb[i-1]=1; } } for(int i=n;i>=1;i--){ if(a[i].first==a[i+1].first){ if(cnta[i+1].r){ cnta[i].r=cnta[i+1].r; } else{ cnta[i+1].r=i+1; cnta[i].r=i+1; } } if(b[i].first==b[i+1].first){ if(cntb[i+1].r){ cntb[i].r=cntb[i+1].r; } else{ cntb[i+1].r=i+1; cntb[i].r=i+1; } } } for(int i=1;i<=n;i++){ if(va[i]){ s1[cnta[i].l].insert({a[i].second,a[i].ind}); } if(vb[i]){ s2[cntb[i].l].insert({b[i].second,b[i].ind}); } } for(int i=1;i<=n;i++){ if(va[i]&&vb[i]){ //cout<<i<<endl; int k=i; //cout<< if(s1[cnta[i].l].size()<=s2[cntb[i].l].size()){ //cout<<1<<endl; for(auto j:s1[cnta[i].l]){ a[k].ind=j.second; a[k].second=j.first; va[k]=0; k++; } } else{ // cout<<2<<endl; for(auto j:s2[cntb[i].l]){ b[k].ind=j.second; b[k].second=j.first; vb[k]=0; k++; } } } if(!va[i]&&!vb[i]){ if(b[i].second>=a[i].second){ // cout<<i<<endl; cout<<"impossible"<<endl;return ; } ans1[i]=a[i].ind; ans2[i]=b[i].ind; } if(va[i]&&!vb[i]){ ans2[i]=b[i].ind; auto temp=s1[cnta[i].l].upper_bound({b[i].second,n+5}); if(temp==s1[cnta[i].l].end()){ // cout<<1<<endl; cout<<"impossible"<<endl; return ; } ans1[i]=(*temp).second; s1[cnta[i].l].erase(temp); } if(!va[i]&&vb[i]){ ans1[i]=a[i].ind; auto temp=s2[cntb[i].l].lower_bound({a[i].second,0}); //cout<<i<<endl; if(temp==s2[cntb[i].l].begin()){ //cout<<2<<endl; cout<<"impossible"<<endl; return ; } temp--; ans2[i]=(*temp).second; s2[cntb[i].l].erase(temp); } } for(int i=1;i<=n;i++){ cout<<ans1[i]<<" "; } cout<<endl; for(int i=1;i<=n;i++){ cout<<ans2[i]<<" "; } cout<<endl; } int main(){ int t=1; //cin>>t; while(t--){ solve(); } }