QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #32215 | #2571. Aidana and Pita | RobeZH# | WA | 406ms | 3852kb | C++ | 2.6kb | 2022-05-18 05:35:59 | 2022-05-18 05:36:00 |
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],cpy[N],n,sum,ans,s[N],now[N];
int it = 0;
bool should_stop() {
return (++it) % 10000 == 0 && (double)clock() / CLOCKS_PER_SEC > 1.9;
}
int ot[N];
void dfs(int pos,int x,int y,int z,int my,int mz){
if(should_stop()){
rep(i,n){
rep(j,n)if(cpy[j]==a[i]){
cpy[j]=0;
ot[j]=s[i];
break;
}
}
//printf("%d\n",ans);
rep(i,n)printf("%d%c",ot[i]," \n"[i==n]);
exit(0);
}
// rep(i,pos-1)printf("%d ",now[i]);
// puts("");
int res=sum-x-y-z,xx=x,yy=y,zz=z;
if(xx>yy)res-=xx-yy,yy=xx;
if(yy>zz)res-=yy-zz,zz=yy;
if(res<0)return;
if(xx+res<yy-my)return;
if(max(0,zz-mz-x)+max(0,zz-mz-y)>res)return;
if(max(0,zz-ans+1-x)+max(0,zz-ans+1-y)>res)return;
if(pos==n+1){
if(z-x<ans){
ans=z-x;
rep(i,n)s[i]=now[i];
}
return;
}
if(a[pos-1]!=a[pos]||now[pos-1]==1){
now[pos]=1;dfs(pos+1,x+a[pos],y,z,my,mz);
}
if(a[pos-1]!=a[pos]||now[pos-1]<=2){
now[pos]=2;dfs(pos+1,x,y+a[pos],z,min(my,a[pos]),mz);
}
now[pos]=3;dfs(pos+1,x,y,z+a[pos],my,min(mz,a[pos]));
}
int tmp[4];
int find(){
tmp[1]=tmp[2]=tmp[3]=0;
rep(i,n)
if(tmp[1]<=tmp[2]&&tmp[1]<=tmp[3])tmp[1]+=a[i];
else if(tmp[2]<=tmp[1]&&tmp[2]<=tmp[3])tmp[2]+=a[i];
else tmp[3]+=a[i];
int ret=0;
ret=max(ret,abs(tmp[1]-tmp[2]));
ret=max(ret,abs(tmp[2]-tmp[3]));
ret=max(ret,abs(tmp[3]-tmp[1]));
return ret;
}
void init(){
ans=sum+1;
sort(a+1,a+n+1);
ans=min(ans,find()+1);
reverse(a+1,a+n+1);
ans=min(ans,find()+1);
rep(tim,100){
random_shuffle(a+1,a+n+1);
ans=min(ans,find()+1);
}
}
int main() {
scanf("%d",&n);
//n=20;
rep(i,n){
scanf("%d",a+i);
//a[i]=i*i;
sum+=a[i],cpy[i]=a[i];
}
init();
sort(a+1,a+n+1);
a[0]=0;a[n+1]=sum+1;
dfs(1,0,0,0,sum,sum);
//printf("%d\n",ans);
rep(i,n){
rep(j,n)if(cpy[j]==a[i]){
cpy[j]=0;
ot[j]=s[i];
break;
}
}
//printf("%d\n",ans);
rep(i,n)printf("%d%c",ot[i]," \n"[i==n]);
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: 3800kb
input:
5 2 3 1 4 2
output:
2 1 1 3 2
result:
ok answer is 0
Test #2:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
6 3 2 5 3 4 2
output:
2 1 3 2 1 3
result:
ok answer is 1
Test #3:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
3 2617460 3290620 1468912
output:
2 3 1
result:
ok answer is 1821708
Test #4:
score: 0
Accepted
time: 406ms
memory: 3812kb
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
output:
2 2 2 3 1 1 1 2 1 3 1 1 2 3 1 2 1 1 2 1 3 3 3 1 2
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 174ms
memory: 3852kb
input:
25 8 2 2 9 9 10 3 5 9 1 2 5 8 1 4 8 4 3 6 2 8 8 4 2 2
output:
1 1 1 1 3 3 1 2 3 1 1 2 2 1 1 2 2 1 3 1 2 3 2 1 1
result:
ok answer is 1
Test #6:
score: -100
Wrong Answer
time: 210ms
memory: 3780kb
input:
25 9999996 9999999 9999991 9999991 9999999 9999997 9999991 9999993 9999992 10000000 9999991 10000000 9999996 9999997 9999993 9999992 9999990 9999991 9999997 10000000 9999998 9999990 9999993 9999990 9999999
output:
2 2 3 3 2 1 3 2 3 1 3 1 2 1 2 3 1 3 2 1 1 1 3 3 2
result:
wrong answer expected 9999943, found 9999950