wa on test18求调
查看原帖
wa on test18求调
312306
LJ07楼主2024/1/10 16:22

显示 wrong answer Vertical lengths sets are not equal (test case 1)

但是我 assert 过了

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define pb emplace_back
#define sz(a) int(a.size())

bool sm;
clock_t stclock;

const int N = 1000;
int h, v;
vi l, p;
bitset<N * N> dp[N + 5];
bool em;

pair<vi, vi> slv(vi &vec)
{
    int s = accumulate(vec.begin(), vec.end(), 0), tot = 0;
    if (s & 1) {
        return make_pair(vi(), vi());
    }
    for (auto &v : vec) {
        dp[tot + 1] = dp[tot] | (dp[tot] << v);
        ++tot;
    }
    if (!dp[tot][s >>= 1]) {
        return make_pair(vi(), vi());
    }
    vi res1, res2;
    reverse(vec.begin(), vec.end());
    for (auto v : vec) {
        if (v <= s && dp[--tot][s - v]) {
            res1.pb(v);
            s -= v;
        }else {
            res2.pb(v);
        }
    }
    return make_pair(res1, res2);
}
void work()
{
    cin >> h;
    l.resize(h);
    for (auto &v : l) {
        cin >> v;
    }
    cin >> v;
    p.resize(v);
    multiset<int> shit;
    for (auto &v : p) {
        cin >> v;
        shit.emplace(v);
    }
    if (h != v) {
        cout << "No\n";
        return ;
    }
    auto [a, b] = slv(l);
    auto [c, d] = slv(p);
    if (!sz(a) || !sz(c)) {
        cout << "No\n";
        return ;
    }
    int x = 0, y = 0, o = 0;
    if (sz(a) <= sz(c)) {
        sort(a.begin(), a.end(), greater<int>()); //绝对值从大到小
        sort(b.begin(), b.end(), greater<int>());
        sort(c.begin(), c.end()); 
        sort(d.begin(), d.end());
    }else {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        sort(c.begin(), c.end(), greater<int>());
        sort(d.begin(), d.end(), greater<int>());
        o = 1;
    }
    for (auto i : b) {
        a.pb(-i);
    }
    for (auto i : d) {
        c.pb(-i);
    }
    auto it1 = a.begin();
    auto it2 = c.begin();
    cout << "Yes\n";
    for (int i = 1; i <= h + v; ++i, o ^= 1) {
        if (o == 0) {
            x += *it1++;
        }else {
            assert(shit.find(abs(*it2)) != shit.end());
            shit.erase(shit.find(abs(*it2)));
            y += *it2++;
        }
        cout << x << ' ' << y << '\n';
    }
}

signed main()
{
    // freopen("input.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    clog << fixed << "mem : " << fabs(&sm - &em) / 1024 / 1024 << endl;
    stclock = clock();

    int test;
    dp[0] = 1;
    for (cin >> test; test--; ) {
        work();
    }
    clog << "time : " << (clock() - stclock) * 1000ll / CLOCKS_PER_SEC << endl;
    return 0;
}
2024/1/10 16:22
加载中...