hdu6136

201708

• 一个堆维护环上所有相邻的人相遇的时间，从中取出最小值
• 删除后，原本不相邻的两个人就相邻了，求出他们的相遇时间，加入堆中
• 重复执行这一过程，直到找到最后一个被淘汰的人为止

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
#define dd(a) cout<<#a<<"="<<a<<" ";
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=100005;
pair<pii,int> a[N];
int n,m,tim;
int l[N],r[N],vis[N];
int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
struct node {
    int i,j,ta,tb;
    node() {}
    node(int _i,int _j) {
        i=_i;j=_j;
        if(a[i].fi.se<a[j].fi.se) swap(i,j);
        ta=(a[j].fi.fi-a[i].fi.fi+m)%m;
        tb=a[i].fi.se-a[j].fi.se;
        int d=gcd(ta,tb);
        ta/=d;tb/=d;
    }
    bool operator < (const node &c) const {
        return 1ll*ta*c.tb>1ll*tb*c.ta;
    }
};
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d%d",&n,&m);
        ///read
        rep(i,1,n+1) {
            int d;scanf("%d",&d);
            a[i].fi.fi=d;
        }
        rep(i,1,n+1) {
            int v;scanf("%d",&v);
            a[i].fi.se=v;
            a[i].se=i;
        }
        ///solve
        ++tim;
        sort(a+1,a+1+n);
        rep(i,1,n) r[i]=i+1;r[n]=1;
        rep(i,2,n+1) l[i]=i-1;l[1]=n;
        priority_queue<node> q;
        if(n>2) q.push(node(1,n));
        rep(i,1,n) q.push(node(i,i+1));
        int ta=0,tb=0;
        while(!q.empty()) {
            node now=q.top();q.pop();
            int i=now.i,j=now.j;
            if(vis[i]==tim||vis[j]==tim) continue;
            int t=(a[i].se>a[j].se)?j:i;
            vis[t]=tim;
            int L=l[t],R=r[t];
            if(L!=R) q.push(node(L,R));
            r[L]=R;l[R]=L;
            ta=now.ta;tb=now.tb;
        }
        ///print
        printf("%d/%d\n",ta,tb);
    }
    return 0;
}