AGC063 C. Add Mod Operations

题目链接：https://atcoder.jp/contests/agc063/tasks/agc063_c

做法

无解的充分必要条件：

存在 $i,j(i\ne j)$ ，使得 $a_i=a_j,b_i\ne b_j$ 。

有解时的构造方法：

设 $c_i$ 表示 $a_i$ 在 $a$ 序列里面从大到小排序的位置。

考虑构造一个这样的序列：$b_i+c_i\ast K$ ，$K$ 表示一个大于所有 $a$ 的数字。

然后最后全部模 $K$ 就行了。

怎么构造这个序列呢？考虑不算次数的情况，那么先把所有数字加个 INF ，然后每次让当前最大的数字变成 $0$，并且再变成 $0$ 之前加上这个数字与前一个变成 $0$ 的数字之间的间隔，然后就做完了。

然后只要精细化的处理一下这个过程，就可以办到恰好 $n$ 次做完这个过程。

时间复杂度：$O(n\log n)$

#include<bits/stdc++.h>
#define N 1100
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
const LL inf=1e16;
LL a[N],b[N];int n;
int top,sta[N];LL now,d[N];
PLL c[N];LL maxcost=0;
inline bool cmp(int x,int y){return a[x]>a[y];}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){scanf("%lld",&b[i]);maxcost=max(maxcost,b[i]+1);}
    for(int i=1;i<=n;i++){
        bool bk=0;
        for(int j=1;j<=n;j++){
            if((a[j]==a[i]) && (b[j]!=b[i])){printf("No\n");return 0;}
            if(j<i && a[j]==a[i])bk=1;
        }
        if(!bk)sta[++top]=i;
    }
    sort(sta+1,sta+top+1,cmp);
    for(int i=1;i<top;i++)d[i]=(top-i-1)*maxcost+b[sta[i]];
    now=inf;LL nowx=now%maxcost;now+=(b[sta[top]]-nowx+maxcost)%maxcost;now-=a[sta[top]];
    c[top].second=maxcost;
    printf("Yes\n%d\n",top);
    for(int i=top;i>=1;i--){
        if(i!=top)c[i].second=now+a[sta[i]];
        if(i!=1)c[i].first=d[i-1]-d[i],now-=c[i].first;
    }
    c[1].first=now;
    if(top==1)c[1].first%=c[1].second;
    for(int i=1;i<=top;i++)printf("%lld %lld\n",c[i].first,c[i].second);
    return 0;
}