QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290083#4617. Arithmetic SubsequenceyspmAC ✓24ms3716kbC++201.4kb2023-12-24 12:36:552023-12-24 12:36:56

Judging History

你现在查看的是最新测评结果

  • [2023-12-24 12:36:56]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:3716kb
  • [2023-12-24 12:36:55]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
template<typename T>inline void ckmax(T &x,T y){x=x<y?y:x;}
template<typename T>inline void ckmin(T &x,T y){x=x>y?y:x;}
template<typename T=int>inline T read(){
    T res=0,f=1; char k;
    while(!isdigit(k=getchar())) if(k=='-') f=-1;
    while(isdigit(k)) res=res*10+k-'0',k=getchar();
    return res*f;
}
template<typename T>inline void print(T x,bool fl=1){
    if(x<0) putchar('-'),x=-x; 
    if(x>=10) print(x/10,0);
    putchar(x%10+'0');
    if(fl) putchar('\n');
}
const int N=5010;
int a[N],b[N],n,ta[N],tb[N];
bool Fail=0;
inline void solve(int l,int r){
    if(r<l) return ;
    if(a[l]==a[r]){
        if(r-l+1>=3) Fail=1;
        return ;
    }
    int c1=l-1,c2=r+1;
    rep(i,l,r) if(a[i]&1) ta[++c1]=a[i]/2,tb[c1]=b[i];
    rep(i,l,r) if(a[i]%2==0) ta[--c2]=a[i]/2,tb[c2]=b[i];
    rep(i,l,r) a[i]=ta[i],b[i]=tb[i];
    solve(l,c1); solve(c2,r);
    return ;
}
int main(){
    int T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;++i) b[i]=a[i]=read();
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        solve(1,n);
        if(Fail){
            Fail=0;
            puts("NO");
            continue;
        }
        puts("YES");
        for(int i=1;i<n;++i) printf("%d ",b[i]);
        printf("%d\n",b[n]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 24ms
memory: 3716kb

input:

25
4
3 6 8 9
5
1 1 1 1 1
5000
204869248 184063453 335277313 805198752 988635160 266844506 494544568 842685418 516257494 110006739 727397507 931812983 898605116 670474885 536302721 818724782 251547299 883494814 479828194 573135914 408419766 283100869 472145517 996777784 393702645 555881361 835407611 ...

output:

YES
3 9 6 8
NO
YES
997457919 28540927 168284159 392485887 30561279 618477055 33609215 425276159 80450303 766389503 20466943 937493759 234127231 266813311 315469695 642043775 876816255 905333631 953092479 284389759 786805119 126109311 668253311 907828351 548105343 857108607 187678847 689291391 927006...

result:

ok