QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #783410 | #9806. Growing Tree | 123456zmy | WA | 0ms | 4152kb | C++14 | 1.2kb | 2024-11-26 09:41:22 | 2024-11-26 09:41:22 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp printf("\n")
#define mo 998244353
using namespace std;
int T,n,m,ans,bz;
int a[2048],d[2048];
vector<int>b[2048];
int dg(int x,int y,int z)
{
if (y>z)return mo;
if (x==0)return y;
int l=1<<x,r=(1<<x+1)-1,zmy=mo;
vector<int>e;
for (int i=l/2;i<=r/2;i++)
{
int u=0,v=0;
vector<int>c;
while (u<b[i*2].size()&&v<b[i*2+1].size())if (b[i*2][u]<b[i*2+1][v])c.pb(b[i*2][u++]);else c.pb(b[i*2+1][v++]);
while (u<b[i*2].size())c.pb(b[i*2][u++]);
while (v<b[i*2+1].size())c.pb(b[i*2+1][v++]);
u=0;
for (int j=1;j<c.size();j++)if (c[j]==c[j-1]){u=1;break;}
if (u)e.pb(i);else b[i]=c;
}
if (y+e.size()>z+1)return mo;
for (int i=0;i<(1<<e.size());i++)
{
for (int j=0;j<e.size();j++)
if ((1<<j)&i)b[e[j]]=b[e[j]*2];else b[e[j]]=b[e[j]*2+1];
zmy=min(zmy,dg(x-1,y+e.size(),z+1));
}
return zmy;
}
int main()
{
scanf("%d",&T);
T=3;
while (T--)
{
scanf("%d",&m);
n=(1<<m+1)-1;
for (int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
d[i]=d[i/2]+a[i];
}
for (int i=1;i<=n;i++)b[i].clear();
for (int i=(1<<m);i<=n;i++)b[i].pb(d[i]);
ans=dg(m,0,0);
if (ans>m)printf("-1\n");else printf("%d\n",ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
input:
3 2 1 2 4 3 2 1 2 1 2 3 3 2 1 2 1 2 3 3 1 1
output:
1 2 -1
result:
ok 3 number(s): "1 2 -1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4152kb
input:
94 5 44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2 3 83 3 74 14 45 17 22 41 62 74 25 1 56 22 7 21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...
output:
2 0 -1
result:
wrong answer Answer contains longer sequence [length = 94], but output contains 3 elements