QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425647 | #2571. Aidana and Pita | ship2077 | AC ✓ | 1054ms | 134816kb | C++14 | 2.9kb | 2024-05-30 15:16:50 | 2024-05-30 15:16:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=531442,inf=0x3f3f3f3f;
vector<tuple<int,int,int,int>>upd[M];
vector<tuple<int,int,int,int>>qry[M];
int n,m,na,nb,lim,ans=inf,ans1,ans2;
int N,num,sum,sum1[1<<13],sum2[1<<13],lsh[M],tr[M],tr1[M],tr2[M];
struct info{int x,y,z,sta1,sta2;
info(int x_=0,int y_=0,int z_=0,int sta1_=0,int sta2_=0)
{x=x_;y=y_;z=z_;sta1=sta1_;sta2=sta2_;}
}a[M],b[1594324];
void init1(){ lim=(1<<m)-1;
auto insert=[&](auto x,auto y,auto sta1,auto sta2){
a[++na]=info(x-y,x+y*2-sum,x*2+y,sta1,sta2);
};
for (int sta=1;sta<=lim;sta++){
int low=sta&-sta;
sum1[sta]=sum1[sta^low]+sum1[low];
}
for (int s=0;s<=lim;s++){
int p=s^lim;insert(sum1[s],0,s,0);
for (int t=p;t;(--t)&=p) insert(sum1[s],sum1[t],s,t);
}
}
void init2(){ lim=(1<<n-m)-1;
auto insert=[&](auto x,auto y,auto sta1,auto sta2){
b[++nb]=info(y-x,-x-y*2,x*2+y-sum,sta1,sta2);
};
for (int sta=1;sta<=lim;sta++){
int low=sta&-sta;
sum2[sta]=sum2[sta^low]+sum2[low];
}
for (int s=0;s<=lim;s++){
int p=s^lim;insert(sum2[s],0,s,0);
for (int t=p;t;(--t)&=p) insert(sum2[s],sum2[t],s,t);
}
}
void update(int x,int p,int sta1,int sta2){
while (x<=num){ if (p<tr[x]) tr[x]=p,tr1[x]=sta1,tr2[x]=sta2; x+=x&-x; }
}
tuple<int,int,int> query(int x){
int ans=inf,ans1,ans2; while (x){ if (tr[x]<ans) ans=tr[x],ans1=tr1[x],ans2=tr2[x]; x-=x&-x; } return make_tuple(ans,ans1,ans2);
}
void solve(){
for (int i=1;i<=na;i++) lsh[++num]=a[i].x;
sort(lsh+1,lsh+num+1);N=num=unique(lsh+1,lsh+num+1)-lsh-1;
for (int i=1;i<=na;i++) a[i].x=lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh;
for (int i=1;i<=nb;i++) b[i].x=lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh;
num=0; for (int i=1;i<=na;i++) lsh[++num]=a[i].y;
sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
for (int i=1;i<=na;i++) a[i].y=lower_bound(lsh+1,lsh+num+1,a[i].y)-lsh;
for (int i=1;i<=nb;i++) b[i].y=lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh;
for (int i=1;i<=na;i++) qry[a[i].x].emplace_back(a[i].y,a[i].z,a[i].sta1,a[i].sta2);
for (int i=1;i<=nb;i++) upd[b[i].x].emplace_back(b[i].y,b[i].z,b[i].sta1,b[i].sta2);
for (int i=1;i<=num;i++) tr[i]=inf;
for (int i=1;i<=N;i++){
for (auto [x,p,sta1,sta2]:upd[i]) update(x,p,sta1,sta2);
for (auto [x,p,sta1,sta2]:qry[i]){
auto [tmp,tmp1,tmp2]=query(x);
if (p+tmp<ans) ans=p+tmp,ans1=sta1|tmp1<<m,ans2=sta2|tmp2<<m;
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;m=n>>1;
for (int i=0;i<n;i++){
int x;cin>>x;sum+=x;
(i<m?sum1[1<<i]:sum2[1<<i-m])=x;
}
init1();init2();solve();
for (int i=0;i<n;i++)
printf("%d%c",ans1>>i&1?1:(ans2>>i&1?2:3)," \n"[i==n-1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 78572kb
input:
5 2 3 1 4 2
output:
3 2 2 1 3
result:
ok answer is 0
Test #2:
score: 0
Accepted
time: 3ms
memory: 78644kb
input:
6 3 2 5 3 4 2
output:
2 3 1 2 3 1
result:
ok answer is 1
Test #3:
score: 0
Accepted
time: 7ms
memory: 78644kb
input:
3 2617460 3290620 1468912
output:
2 1 3
result:
ok answer is 1821708
Test #4:
score: 0
Accepted
time: 137ms
memory: 115292kb
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:
3 2 3 3 2 3 2 2 2 2 2 2 1 1 1 1 3 1 1 1 1 1 3 3 3
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 138ms
memory: 115468kb
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:
2 3 3 3 2 3 2 2 2 2 2 2 1 1 1 1 1 1 1 3 1 3 3 3 3
result:
ok answer is 1
Test #6:
score: 0
Accepted
time: 232ms
memory: 119308kb
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 1 1 2 3 1 2 2 2 1 2 2 3 3 1 1 1 3 3 3 1 3 1 3
result:
ok answer is 9999943
Test #7:
score: 0
Accepted
time: 67ms
memory: 118100kb
input:
25 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000
output:
3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 3 3 3 3
result:
ok answer is 10000000
Test #8:
score: 0
Accepted
time: 902ms
memory: 133412kb
input:
25 4568194 6252832 2990361 6179671 5525735 3402540 12193 4812907 2393092 9823299 4089880 1724585 2200631 5143163 5750864 5341161 5957736 2310544 8033121 9675751 9295231 71902 6463783 7667395 5613033
output:
1 3 3 3 3 3 2 2 2 1 1 3 3 2 3 1 1 1 2 1 2 3 2 3 2
result:
ok answer is 49
Test #9:
score: 0
Accepted
time: 968ms
memory: 133388kb
input:
25 7762025 9149481 7523209 4813111 6800820 1960599 4807700 5411348 4528299 7599785 3468951 537831 6539799 2655771 1259341 9722159 506693 2973008 7910966 3611985 6228870 4141646 9112851 1735188 6538160
output:
3 1 2 3 1 3 3 2 3 3 2 2 3 3 3 1 3 1 1 2 2 1 2 1 2
result:
ok answer is 145
Test #10:
score: 0
Accepted
time: 918ms
memory: 133472kb
input:
25 4732744 6239034 6860504 9029957 848680 209411 3629865 1309532 7860007 2831327 1707125 320774 4082248 4458046 8318819 7279399 861428 5020696 716989 8764261 952311 9612131 5994738 7283372 5509248
output:
3 3 3 1 3 3 3 2 2 3 2 2 2 1 1 2 1 2 1 1 2 2 1 3 3
result:
ok answer is 53
Test #11:
score: 0
Accepted
time: 964ms
memory: 134816kb
input:
25 3926971 5832018 518527 8763702 973269 4552634 6533999 2808656 1277522 5063756 3389181 9876771 4222160 9001717 3592108 5852492 7874646 507942 8922016 4798000 1131210 9081684 512549 3399413 3253241
output:
3 2 2 1 3 2 3 2 2 1 2 1 2 3 3 2 3 2 1 1 1 2 2 3 3
result:
ok answer is 91
Test #12:
score: 0
Accepted
time: 933ms
memory: 134524kb
input:
25 9383440 7906533 1692080 1331860 34750 3968473 2920448 8420499 271149 5986045 9894611 508079 1328124 2344042 9426700 8381332 7038317 4146561 5946221 3554163 215270 6084580 2549278 2162818 3791345
output:
1 2 1 3 3 3 3 1 3 2 1 2 3 3 3 2 1 2 2 2 3 3 3 3 3
result:
ok answer is 110
Test #13:
score: 0
Accepted
time: 949ms
memory: 133716kb
input:
25 4046088 7315708 7288467 1966990 9827334 4635838 8767858 753173 7611802 8291513 4297560 3224050 8917952 5408746 3999749 761012 1332251 409871 2394270 1464938 7524338 2072107 3597866 4231339 9638829
output:
2 3 2 2 1 1 2 1 1 3 3 2 3 1 2 1 1 2 2 3 1 1 2 2 3
result:
ok answer is 101
Test #14:
score: 0
Accepted
time: 972ms
memory: 134492kb
input:
25 5547618 2099625 1573205 2912509 2335015 318412 5812834 9389294 7275632 2026666 7297673 3627332 1756646 7605338 5450938 6407663 678114 5237576 4788058 1293302 5458419 9269556 9795138 6180722 2919003
output:
3 2 3 3 2 2 3 1 2 3 1 3 3 3 1 1 1 3 2 2 2 2 1 2 3
result:
ok answer is 93
Test #15:
score: 0
Accepted
time: 1054ms
memory: 134004kb
input:
25 58653 5582060 2162966 9667782 5952067 1573434 692941 6120542 1083586 5478323 762427 4922098 3516225 9558027 2481388 1525866 1640140 5470075 6840333 8007024 520149 1766849 496240 7801716 7498415
output:
2 1 2 2 3 1 3 1 3 3 3 3 2 2 1 2 1 2 3 1 1 2 3 1 3
result:
ok answer is 23
Test #16:
score: 0
Accepted
time: 292ms
memory: 122608kb
input:
25 911 78 35 7 73 7 74 57 40 54 71 15 78 931 29 51 12 953 47 18 44 51 27 62 16
output:
2 3 2 2 2 2 2 3 3 2 2 2 1 3 1 1 3 1 1 1 1 3 1 3 3
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 709ms
memory: 131256kb
input:
25 56582 31593 65868 9990302 89743 29492 69983 10894 37205 19856 32444 9930060 97648 56666 17128 53655 30899 48933 58260 51304 83008 96129 1061 11962 9941936
output:
1 2 3 2 2 2 1 3 2 3 3 3 3 1 1 1 2 1 1 3 2 3 1 2 1
result:
ok answer is 1
Test #18:
score: 0
Accepted
time: 154ms
memory: 125364kb
input:
25 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 6257913
output:
3 3 2 2 2 2 2 3 3 2 2 2 2 2 3 2 2 2 2 2 3 2 2 1 3
result:
ok answer is 1065348
Test #19:
score: 0
Accepted
time: 256ms
memory: 129000kb
input:
25 1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 1088916 1520954 9015711 5552512 1853562 2760187 8617948 6012543 456601 6151460
output:
3 3 3 3 3 3 2 3 2 2 3 1 2 3 1 2 3 1 3 3 1 2 2 2 3
result:
ok answer is 1603
Test #20:
score: 0
Accepted
time: 354ms
memory: 121708kb
input:
25 1 10 100 1000 10000 100000 1000000 10000000 69 45 74 74 33 29 35 55 1 43 50 86 10 81 29 96 73
output:
3 3 3 3 3 3 2 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
result:
ok answer is 9888006
Test #21:
score: 0
Accepted
time: 141ms
memory: 120460kb
input:
25 1 15 225 3375 50625 759375 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
3 3 3 3 2 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
result:
ok answer is 755740
Test #22:
score: 0
Accepted
time: 149ms
memory: 125236kb
input:
25 1 20 400 8000 160000 3200000 1 1 1 1 1 1 1 2 1 2 1 2 1 2 2 2 2 2 2
output:
3 3 3 3 2 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
result:
ok answer is 3191551
Test #23:
score: 0
Accepted
time: 747ms
memory: 133296kb
input:
25 63353 736041 846599 1431744 1739144 2274384 2726277 3192576 3288972 3897012 4065841 4471346 4818261 5270407 5717802 6224939 6449270 6970979 7252374 7847142 8218821 8775107 8869918 9324673 9686751
output:
2 3 1 1 1 3 3 2 1 2 2 3 1 2 3 1 3 1 2 1 1 2 2 3 3
result:
ok answer is 57