https://codeforces.com/contest/1428/problem/D
这题写到2小时多才过。。。
观察发现从左到右,a[j]=3的右边的列可以是a[j]=3,2,1,然而a[j]=2右边的列必须是a[j]=1,a[j]=1时碰撞的那个target右边必没有再一个target。
从左到右非常难写，写了半天也绕不清
然后发现从右到左非常好写。。。
对于a[j]=1时，可知他右边没有多的target，我们必须新开一行。又因为如果有多个a[j]=3连在一起，从右到左横坐标只会不断变小，所以up从n开始不断变小，出现一个a[j]=1，up--
对于a[j]=2时，他右边的列必须是a[j]=1，所以就用一个栈来记录还有哪些1没有被2匹配，然后让2匹配一个a[j]=1的列，此时就是那一行上多一个target，x就是那个a[j]=1的列的x
对于a[j]=3，我们连3还是连2还是连1都必须新开一行，而a[j]=1是稀有资源，所以连3还是2都无所谓
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=3e5+10; int n,m,cnt,tot2,cas,ans,cnt3,cnt2,cnt1; int a[maxl],col[maxl][2],num[maxl]; int ind3[maxl],ind2[maxl],ind1[maxl]; struct node { int x,y; }c[maxl*2]; char s[maxl]; inline void prework() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) if(a[i]==2) tot2++; } inline void mainwork() { int up=n,sum2=0; for(int i=n;i>=1;i--) { if(a[i]==0) continue; if(a[i]==1) { if(up<=0){ans=-1;return;} col[i][0]=up; up--; ind1[++cnt1]=i; } if(a[i]==2) { if(cnt1==0){ans=-1;return;} col[i][0]=col[ind1[cnt1]][0]; cnt1--;sum2++; ind2[++cnt2]=i; } if(a[i]==3) { if(up<=0){ans=-1;return;} if(cnt3>0) { col[i][0]=up; col[ind3[cnt3]][1]=up; ind3[cnt3]=i; }else if(cnt2>0) { col[i][0]=up; col[ind2[cnt2]][1]=up; ind3[++cnt3]=i; cnt2--; } else if(cnt1>0) { col[i][0]=up; col[ind1[cnt1]][1]=up; ind3[++cnt3]=i; cnt1--; } else { ans=-1; return; } up--; } } ans=0; for(int j=1;j<=n;j++) { if(col[j][0]>0) c[++ans]=node{col[j][0],j}; if(col[j][1]>0) c[++ans]=node{col[j][1],j}; } for(int i=1;i<=ans;i++) if(c[i].x>n || c[i].x<1) ans=-1; } inline void print() { if(ans<0) puts("-1"); else { printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d %d\n",c[i].x,c[i].y); } } int main() { int t=1; //scanf("%d",&t); for(cas=1;cas<=t;cas++) { prework(); mainwork(); print(); } return 0; }
