Submission #1150536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150536		The_Samurai	Tug of War (BOI15_tug)	C++20	0 / 100	169 ms	8560 KiB

tug

// I stand with PALESTINE



//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

// #define int long long
#define ff first
#define ss second
#define sz(a) (int) (a).size()
//template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;

namespace io {

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; }

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const map<F, S> &mp) {
        for (auto it: mp) { os << it << endl; }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const vector<F> &v) {
        bool space = false;
        for (F x: v) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const deque<F> &d) {
        bool space = false;
        for (F x: d) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const set<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const multiset<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x << x;
        }
        return os;
    }

    template<typename F, typename S>
    istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; }

    template<typename F>
    istream &operator>>(istream &is, vector<F> &v) {
        for (F &x: v) { is >> x; }
        return is;
    }

    long long fastread() {
        char c;
        long long d = 1, x = 0;
        do c = getchar(); while (c == ' ' || c == '\n');
        if (c == '-') c = getchar(), d = -1;
        while (isdigit(c)) {
            x = x * 10 + c - '0';
            c = getchar();
        }
        return d * x;
    }

    static bool sep = false;

    using std::to_string;

    string to_string(bool x) {
        return (x ? "true" : "false");
    }

    string to_string(const string &s) { return "\"" + s + "\""; }

    string to_string(const char *s) { return "\"" + string(s) + "\""; }

    string to_string(const char &c) {
        string s;
        s += c;
        return "\'" + s + "\'";
    }

    template<typename Type>
    string to_string(vector<Type>);

    template<typename F, typename S>
    string to_string(pair<F, S>);

    template<typename Collection>
    string to_string(Collection);

    template<typename F, typename S>
    string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; }

    template<typename Type>
    string to_string(vector<Type> v) {
        bool sep = false;
        string s = "[";
        for (Type x: v) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "]";
        return s;
    }

    template<typename Collection>
    string to_string(Collection collection) {
        bool sep = false;
        string s = "{";
        for (auto x: collection) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "}";
        return s;
    }

    void print() {
        cout << endl;
        sep = false;
    }

    template<typename F, typename... Other>
    void print(F ff, Other... other) {
        if (sep) cout << " | ";
        sep = true;
        cout << to_string(ff);
        print(other...);
    }

}
using namespace io;

namespace utils {

    template<typename F, typename S>
    inline void maxs(F &a, S b) { a = a > b ? a : b; }

    template<typename F, typename S>
    inline void mins(F &a, S b) { a = a < b ? a : b; }

    template<typename F, typename S>
    long long max(F a, S b) { return a > b ? a : b; }

    template<typename F, typename S>
    long long min(F a, S b) { return a < b ? a : b; }

    constexpr long long operator "" _E(unsigned long long n) {
        long long p = 1, a = 10;
        for (int i = 0; i < n; i++) p *= a;
        return p;
    }

    random_device rd;
    mt19937 mt(rd());

    template<typename T>
    T rand(T l, T r) {
        uniform_int_distribution<T> dist(l, r);
        return dist(mt);
    };

}
using namespace utils;


#ifdef sunnatov
#define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ );
#else
#define print( ... ) 42
#endif

const int mod = 9_E + 7;
const double EPS = 1e-7;
long long doxuya = 18_E + 10;
int INF = 9_E + 10;
const char nl = '\n';

int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

/*

*/

struct custom_bitset {
    vector<uint64_t> bits;
    int64_t b, n;
 
    custom_bitset(int64_t _b = 0) {
        init(_b);
    }
 
    void init(int64_t _b) {
        b = _b;
        n = (b + 63) / 64;
        bits.assign(n, 0);
    }
 
    void clear() {
        b = n = 0;
        bits.clear();
    }
 
    void reset() {
        bits.assign(n, 0);
    }
 
    void _clean() {
        // Reset all bits after `b`.
        if (b != 64 * n)
            bits.back() &= (1LLU << (b - 64 * (n - 1))) - 1;
    }
 
    bool get(int64_t index) const {
        return bits[index / 64] >> (index % 64) & 1;
    }
 
    void set(int64_t index, bool value) {
        assert(0 <= index && index < b);
        bits[index / 64] &= ~(1LLU << (index % 64));
        bits[index / 64] |= uint64_t(value) << (index % 64);
    }
 
    // Simulates `bs |= bs << shift;`
    void or_shift(int64_t shift) {
        int64_t div = shift / 64, mod = shift % 64;
 
        if (mod == 0) {
            for (int64_t i = n - 1; i >= div; i--)
                bits[i] |= bits[i - div];
 
            return;
        }
 
        for (int64_t i = n - 1; i >= div + 1; i--)
            bits[i] |= bits[i - (div + 1)] >> (64 - mod) | bits[i - div] << mod;
 
        if (div < n)
            bits[div] |= bits[0] << mod;
 
        _clean();
    }
 
    // Simulates `bs |= bs >> shift;`
    void or_shift_down(int64_t shift) {
        int64_t div = shift / 64, mod = shift % 64;
 
        if (mod == 0) {
            for (int64_t i = div; i < n; i++)
                bits[i - div] |= bits[i];
 
            return;
        }
 
        for (int64_t i = 0; i < n - (div + 1); i++)
            bits[i] |= bits[i + (div + 1)] << (64 - mod) | bits[i + div] >> mod;
 
        if (div < n)
            bits[n - div - 1] |= bits[n - 1] >> mod;
 
        _clean();
    }
 
    int64_t find_first() const {
        for (int i = 0; i < n; i++)
            if (bits[i] != 0)
                return 64 * i + __builtin_ctzll(bits[i]);
 
        return -1;
    }
 
    custom_bitset& operator&=(const custom_bitset &other) {
        assert(b == other.b);
 
        for (int i = 0; i < n; i++)
            bits[i] &= other.bits[i];
 
        return *this;
    }
};

void solution(istream &cin, ostream &cout, const int &test_case) {
    int n, k;
    cin >> n >> k;
    vector<int> l(2 * n + 1), r(2 * n + 1), w(2 * n + 1);
    vector<set<int>> have(4 * n + 1);
    for (int i = 1; i <= 2 * n; i++) {
        cin >> l[i] >> r[i] >> w[i];
        l[i] += 2 * n;
        r[i] += 3 * n;
        have[l[i]].insert(i);
        have[r[i]].insert(i);
        have[i].insert(l[i]);
        have[i].insert(r[i]);
    }

    // clearing
    set<pair<int, int>> st;
    vector<bool> used(4 * n + 1);
    for (int i = 1; i <= 4 * n; i++) st.emplace(sz(have[i]), i);
    array<int, 2> sum{};
    while (!st.empty() and st.begin()->first <= 1) {
        auto [_, i] = *st.begin(); st.erase(st.begin());
        if (have[i].empty()) {
            cout << "NO";
            return;
        }
        int j = *have[i].begin(); have[i].clear();
        used[i] = used[j] = true;
        if (i <= 2 * n) sum[(j - 2 * n) / n] += w[i];
        else sum[(i - 2 * n) / n] += w[j];
        for (int p: have[j]) {
            if (st.find(make_pair(sz(have[p]), p)) != st.end()) {
                st.erase(make_pair(sz(have[p]), p));
                have[p].erase(j);
                st.emplace(sz(have[p]), p);
            }
        }
    }


    // endi hammasi 2
    print(have);
    vector<pair<int, int>> variants;
    for (int i = 1; i <= 2 * n; i++) {
        if (used[i]) continue;
        vector<int> way = {i}; 
        used[i] = true;
        while (true) {
            bool found = false;
            for (int x: have[way.back()]) {
                if (used[x]) continue;
                way.emplace_back(x);
                used[x] = true;
                found = true;
                break;
            }
            if (!found) break;
        }
        variants.emplace_back(0, 0);
        for (int j = 0; j < sz(way); j += 2) {
            assert(way[j] <= 2 * n);
            if (j % 4 == 2) variants.back().ss += w[way[j]];
            else variants.back().ff += w[way[j]];
        }
    }


    print(variants);
    int all = 0;
    for (int i = 1; i <= 2 * n; i++) all += w[i];
    const int N = 3e5 + 1;
    bitset<N> bs; bs.set(0, true);
    for (auto [v1, v2]: variants) {
        bs = (bs << v1) | (bs << v2);
        // auto nw = bts;
        // bts.or_shift(v1); nw.or_shift(v2);
        // bts &= nw;
        // for (int i = 0; i <= all; i++) cout << bts.get(i) << ' ';
        // cout << endl;
    }
    int diff = INF;
    for (int i = 1; i <= all / 2; i++) {
        if (bs[i]) {
            mins(diff, abs(i + sum[0] - (all - i + sum[1])));
            mins(diff, abs(i + sum[1] - (all - i + sum[0])));
        }
    }
    print(diff, all);

    cout << (diff <= k ? "YES" : "NO");
}

int32_t main() {
    clock_t startTime = clock();
    cin.tie(0)->sync_with_stdio(false);
    srand(time(0));

    std::istream &in(std::cin);
    std::ostream &out(std::cout);

    int32_t queries = 1;

#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    // cin >> queries;
#endif

    for (int32_t test_case = 1; test_case <= queries; test_case++) {
        print(test_case);
        solution(cin, cout, test_case);
        cout << nl;
    }

#ifdef sunnatov
    cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return EXIT_SUCCESS;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29