C - Large Summation
Time Limit:1000MS Memory Limit:262144KB
CFGym 101532C
use MathJax to parse formulas
Description
You are given an array a consisting of n element a1,?a2,?...,?an. For each element ai you must find another element aj(i?≠?j), such that the summation of ai and ajmod (109 + 7) (i.e. (ai?+?aj) % (109 + 7)) is as maximal as possible.
Can you help judges by solving this hard problem?
Input
The first line contains an integer T, where T is the number of test cases.
The first line of each test contains an integer n(2?≤?n?≤?105), where n is the size of the array a.
The second line of each test case contains n integers a1,?a2,?...,?an(0?≤?ai?<?109?+?7), giving the array a.
Output
For each test case, print a single line containing n space separated elements, such that the ith element is the answer to the ith element in the array a (i.e. the maximum value of (ai?+?aj) % (109 + 7)).
Sample Input
Input
2 3 1 2 3 2 1000000000 1000000000
Output
4 5 5 999999993 999999993
代码过于复杂，不推荐使用
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;struct A
{ll x,num;
}b[200200];ll M=1000000007;
ll n;
ll a[200200],ans[200200];
map<ll,ll> mp,per;
bool cmp(A a,A b)
{return a.x<b.x;
}ll ef(ll w)
{ll l=1,r=n;while(1){ll mid=(r+l)/2;if(w<=b[mid].x){r=mid;}else{l=mid+1;}if(l==r){if(b[l].x>w)l--;if(l==0)l++;return l;}if(l>r)break;}return l;
}
int main()
{int T;scanf("%d",&T);while(T--){mp.clear();scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);mp[a[i]]++;b[i].x=a[i];b[i].num=i;}if(n==1){cout<<a[1]<<endl;continue;}ll ww=a[1],u;for(u=1;u<=n;u++){if(a[u]!=ww)break;}if(u==n+1){printf("%lld",a[1]*2%M);for(ll i=2;i<=n;i++)printf(" %lld",a[1]*2%M);printf("\n");continue;}sort(b+1,b+1+n,cmp);ll mx1=-1,mx2=-1;per[b[1].x]=-1;ll t=b[1].x;for(ll i=2;i<=n;i++){if(t!=b[i].x)per[b[i].x]=t;t=b[i].x;mx1=max(mx1,b[i].x);}for(ll i=1;i<=n;i++){if(b[i].x!=mx1)mx2=max(mx2,b[i].x);}for(ll i=1;i<=n;i++){ll s1,s2;ll t=M-a[i]-1;ll w=ef(t);if(b[w].x==a[i]){if(mp[a[i]]>=2)s1=a[i];elses1=per[a[i]];}elses1=b[w].x;if(s1==-1)s1=M-a[i];if(a[i]==mx1){if(mp[mx1]>=2)s2=mx1;elses2=mx2;}elses2=mx1;if(s2==-1)s2=M-a[i];ans[i]=max((a[i]+s1)%M,(a[i]+s2)%M);}printf("%lld",ans[1]);for(ll i=2;i<=n;i++)printf(" %lld",ans[i]);printf("\n");}return 0;
}