容易发现要么1和n直接相连,要么两点距离即为所有d+d的最小值。若为前者,需要满足所有|d-d|都相等,挂两棵菊花即可。若为后者,将所有满足d+d=d的挂成一条链,其余点直接与链上点相连即可,相连点需要满足d-d=d-d。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 500010
#define D 1000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,a[N],b[N],id[D];
struct data
{
int x,i;
bool operator <(const data&a) const
{
return x<a.x;
}
}d[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj5100.in","r",stdin);
freopen("bzoj5100.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<n;i++) a[i]=read();
for (int i=;i<n;i++) b[i]=read();
if (n==) {cout<<"TAK\n"<<endl<<<<' '<<<<' '<<;return ;}
int len=abs(a[]-b[]);
for (int i=;i<n;i++) if (abs(a[i]-b[i])!=len) {len=;break;}
if (len)
{
cout<<"TAK\n";
cout<<<<' '<<n<<' '<<len<<endl;
for (int i=;i<n;i++)
if (a[i]>b[i]) printf("%d %d %d\n",i,n,b[i]);
else printf("%d %d %d\n",i,,a[i]);
return ;
}
len=;
for (int i=;i<n;i++) len=min(len,a[i]+b[i]);
int cnt=;for (int i=;i<n;i++) if (a[i]+b[i]==len) cnt++,d[cnt].x=a[i],d[cnt].i=i;
sort(d+,d+cnt+);++cnt;d[].x=,d[].i=,d[cnt].x=len,d[cnt].i=n;
for (int i=;i<=cnt;i++) if (d[i].x==d[i-].x) {cout<<"NIE";return ;}
for (int i=;i<=cnt;i++) id[d[i].x]=d[i].i;
for (int i=;i<n;i++)
if (a[i]+b[i]>len&&((a[i]+b[i]-len&)||!id[a[i]-(a[i]+b[i]-len>>)])) {cout<<"NIE";return ;}
cout<<"TAK\n";
for (int i=;i<=cnt;i++) printf("%d %d %d\n",d[i-].i,d[i].i,d[i].x-d[i-].x);
for (int i=;i<n;i++)
if (a[i]+b[i]>len) printf("%d %d %d\n",id[a[i]-(a[i]+b[i]-len>>)],i,a[i]+b[i]-len>>);
return ;
}
04-25 06:35