QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #32224 | #2571. Aidana and Pita | RobeZH# | TL | 3ms | 5960kb | C++ | 1.5kb | 2022-05-18 06:09:51 | 2022-05-18 06:09:52 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
const int N=30;
int a[N],n;
int dp[1<<25],to[1<<25],iss[1<<25],sum=0;
int ot[N];
int main() {
for(int i=0;i<25;++i)iss[1<<i]=i;
scanf("%d",&n);
//n=25;
rep(i,n){
scanf("%d",a+i);
//a[i]=i*i;
sum+=a[i];
}
ot[n]=3;
--n;
for(int mk=1;mk<1<<n;++mk){
dp[mk]=sum;
for(int tmp=mk,j=iss[tmp&-tmp];tmp;tmp-=1<<j,j=iss[tmp&-tmp]){
int now=dp[mk-(1<<j)];
if(now<0)now+=a[j+1];else now-=a[j+1];
if(abs(now)<abs(dp[mk])){
dp[mk]=now;
to[mk]=j;
}
}
}
int ans=sum+1,is=0;
for(int mk=0;mk<1<<n;++mk){
int s=0;
for(int tmp=mk,j=iss[tmp&-tmp];tmp;tmp-=1<<j,j=iss[tmp&-tmp]){
s+=a[j+1];
}
int u=s+a[n+1],v=(sum-s-dp[(1<<n)-1-mk])/2,w=(sum-s+dp[(1<<n)-1-mk])/2;
int nw=max(abs(u-v),max(abs(v-w),abs(w-u)));
if(ans>nw){
ans=nw;
is=(1<<n)-1-mk;
}
}
for(int j=0;j<n;++j)if(!(is&(1<<j)))ot[j+1]=3;
while(is>0){
int nxt=is-(1<<to[is]);
ot[to[is]+1]=(dp[nxt]<0?1:2);
is=nxt;
}
//printf("%d\n",ans);
rep(i,n+1)printf("%d%c",ot[i]," \n"[i==n+1]);
return 0;
}
/*
20
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5960kb
input:
5 2 3 1 4 2
output:
3 1 1 2 3
result:
ok answer is 0
Test #2:
score: 0
Accepted
time: 2ms
memory: 5804kb
input:
6 3 2 5 3 4 2
output:
1 2 3 1 2 3
result:
ok answer is 1
Test #3:
score: 0
Accepted
time: 3ms
memory: 5888kb
input:
3 2617460 3290620 1468912
output:
1 2 3
result:
ok answer is 1821708
Test #4:
score: -100
Time Limit Exceeded
input:
25 6 6 7 8 5 10 5 7 10 10 4 4 5 8 1 6 3 1 9 4 10 7 8 4 5