QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #783377 | #9806. Growing Tree | 123456zmy | WA | 2ms | 4112kb | C++14 | 1.3kb | 2024-11-26 09:21:23 | 2024-11-26 09:21:23 |
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,o=0,id,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;
//for (int j=0;j<c.size();j++)printf("%d ",c[j]);pp;
}
for (int i=0;i<(1<<e.size());i++)
{
for (int j=0;j<e.size();j++)
if ((j<<1)&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);
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);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4112kb
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: 2ms
memory: 3848kb
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:
3 0 -1 2 0 1 -1 0 0 4 0 0 0 1 2 1 0 2 0 2 0 -1 0 -1 0 0 -1 -1 -1 -1 -1 4 -1 0 4 2 7 -1 -1 -1 1 2 5 0 0 2 -1 1 7 0 -1 2 -1 0 0 0 -1 1 -1 -1 0 0 1 1 -1 0 1 2 0 -1 0 0 1 1 -1 0 -1 0 0 0 -1 3 -1 1 7 0 0 0 0 1 0 -1 4 3
result:
wrong answer 1st numbers differ - expected: '2', found: '3'