QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#411905 | #6746. Merge the Rectangles | Ynoiynoi# | WA | 0ms | 3680kb | C++14 | 2.5kb | 2024-05-15 21:21:39 | 2024-05-15 21:21:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define int long long
const int INF = 1e18;
int n,m;
int a[MAXN];
struct aa {
int a[MAXN],nn;
void wt() {
for(int i = 1; i <= nn; i ++)
cout<<a[i]<<" ";
cout<<"\n";
}
};
aa merge(aa a,aa b) {
aa c;
c.nn = 0;
c.nn = a.nn+b.nn;
for(int i = 1; i <= a.nn; i ++)
c.a[i] = a.a[i];
for(int i = 1; i <= b.nn; i ++)
c.a[i+a.nn] = b.a[i];
return c;
}
bool operator <(aa a,aa b) {
for(int i = 1; i <= a.nn; i ++) {
if(a.a[i] > b.a[i]) return 0;
if(a.a[i] < b.a[i]) return 1;
}
return 0;
}
aa f[MAXN],b[MAXN];
int c[MAXN],zw[MAXN];
int lc[MAXN],rc[MAXN];
void dfs(int x) {
// cout<<x<<"\n";
if(a[x] != 0) {
f[x].nn = 1;
f[x].a[1] = a[x];
b[x] = f[x];
return;
}
dfs(lc[x]);
dfs(rc[x]);
b[x] = merge(b[lc[x]],b[rc[x]]);
c[x] = c[lc[x]]+c[rc[x]];
aa f1 = merge(f[lc[x]],f[rc[x]]);
aa f2 = merge(f[rc[x]],f[lc[x]]);
zw[x] = zw[lc[x]]+zw[rc[x]];
if(f1 < f2) {
f[x] = f1;
return;
} else {
f[x] = f2;
if(f2 < f1) c[x] ++;
else zw[x] = -INF;
return;
}
}
int rt;
int ew[MAXN];
aa p[MAXN];
int zp[MAXN];
aa orz(int x,int m) {
//cout<<x<<" "<<m<<"\n";
if(a[x] != 0) return b[x];
if(m == 0) {
return b[x];
}
// if(m >= c[x]) return f[x];
aa f1,f2;
bool d1 = 0,d2 = 0;
if(c[lc[x]] <= m) {
d1 = 1; f1 = merge(f[lc[x]],orz(rc[x],m-c[lc[x]]));
} else f1 = merge(orz(lc[x],m),b[rc[x]]);
if(c[rc[x]] <= m-1) {
d2 = 1; f2 = merge(f[rc[x]],orz(lc[x],m-1-c[lc[x]]));
} else f2 = merge(orz(rc[x],m-1),b[lc[x]]);
/* cout<<x<<":----\n";
f1.wt();
f2.wt();*/
if(f1 < f2) {
if(d1) zp[x] = zw[lc[x]] + zp[rc[x]];
else zp[x] = zp[lc[x]];
return f1;
} else {
if(f2 < f1) {
if(d2) zp[x] = zp[lc[x]]+zw[rc[x]]+1;
else zp[x] = zp[rc[x]]+1;
} else zp[x] = -INF;
return f2;
}
}
int cc[MAXN];
bool eq(aa a,aa b) {
for(int i = 1; i <= a.nn; i ++)
if(a.a[i] != b.a[i]) return 0;
return 1;
}
aa an;
aa w[MAXN];
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
int op;
cin >> op;
if(op == 1) {
cin >> lc[i] >> rc[i];
} else cin >> a[i];
}
dfs(1);
an = orz(1,m);/*
for(int i = 1; i <= n; i ++)
cout<<zp[i]<<" ";
cout<<"\n";*/
if(zp[1] > 0 && zp[1]%2 != m%2) swap(an.a[an.nn],an.a[an.nn-1]);
for(int i = 1; i <= an.nn; i ++)
cout<<an.a[i]<<" ";
return 0;
}
/*
7 1
1 2 3
1 4 5
1 6 7
2 4
2 2
2 3
2 1
3 2
1 2 3
2 2
2 1
*/
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3680kb
input:
3 4 0000 0111 101 101 110
output:
111
result:
wrong output format YES or NO expected, but 111 found