QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290083 | #4617. Arithmetic Subsequence | yspm | AC ✓ | 24ms | 3716kb | C++20 | 1.4kb | 2023-12-24 12:36:55 | 2023-12-24 12:36:56 |
Judging History
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