Submission #1170401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170401		patgra	Minerals (JOI19_minerals)	C++20	100 / 100	44 ms	3932 KiB

minerals

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#include "minerals.h"

constexpr int maxn = 43007 * 2;
bool isIn[maxn];
int cntIn;
int n;
int curPairs;
mt19937 rnd(2137);

int myQuery(int i) {
    if(isIn[i]) cntIn--;
    else cntIn++;
    isIn[i] = !isIn[i];
    int ret = cntIn - Query(i + 1);
    DC << " ============  Querying " << i << " -> " << ret << eol;
    return ret;
}

void dq(vector<int> h1, vector<int> h2, bool in1) {
    ranges::shuffle(h1, rnd);
    ranges::shuffle(h2, rnd);
    assert(h1.size() == h2.size());
    DEBUG {
        DC << "D&Q\n h1: {";
        repIn(i, h1) DC << i << ", ";
        DC << "}\n h2: {";
        repIn(i, h2) DC << i << ", ";
        DC << "}\n in1 " << in1 << " ; in2 " << eol;
        repIn(i, h1) assert(isIn[i] == in1);
        //repIn(i, h2) assert(isIn[i] == in2);
    }
    int sz = (int)h1.size(), m = sz / 2;
    if(sz == 1) { Answer(h1.back() + 1, h2.back() + 1); return; }
    vector<int> lh1, lh2, rh1, rh2;
    rep(i, 0, m) lh1.pb(h1[i]);
    rep(i, m, sz) rh1.pb(h1[i]);

    int cntIn2 = 0;
    repIn(i, h2) cntIn2 += isIn[i];
    if(abs(cntIn2 - m) < m) {
        vector<int> tmp;
        repIn(i, h2) if(isIn[i]) tmp.pb(i);
        repIn(i, h2) if(!isIn[i]) tmp.pb(i);
        swap(h2, tmp);
        swap(h1, h2);
        lh1.clear(); rh1.clear();
        rep(i, 0, sz) {
            if(i < m) {
                if(!isIn[h1[i]]) curPairs = myQuery(h1[i]);
                lh1.pb(h1[i]);
            }
            else {
                if(isIn[h1[i]]) curPairs = myQuery(h1[i]);
                rh1.pb(h1[i]);
            }
        }
    }
    else { 
        int toDel1 = -1, toDel2 = -1;
        rep(i, in1 ? m : 0, in1 ? sz : m) {
            auto newPairs = myQuery(h1[i]);
            /*
            if(newPairs == curPairs) repIn(j, h2) if(isIn[j]) surelyNot[h1[i]].insert(j), surelyNot[j].insert(h1[i]);
            if(newPairs != curPairs) repIn(j, h2) if(!isIn[j]) surelyNot[h1[i]].insert(j), surelyNot[j].insert(h1[i]);
            */
            if(newPairs != curPairs && cntIn2 == 1) {
                int theOne = 0;
                repIn(j, h2) if(isIn[j]) { theOne = j; break; }
                Answer(h1[i] + 1, theOne + 1);
                toDel1 = h1[i];
                toDel2 = theOne;
            }
            if(newPairs == curPairs && cntIn2 + 1 == h2.size()) {
                int theOne = 0;
                repIn(j, h2) if(!isIn[j]) { theOne = j; break; }
                Answer(h1[i] + 1, theOne + 1);
                toDel1 = h1[i];
                toDel2 = theOne;
            }
            curPairs = newPairs;
        }
        vector<int> tmp;
        repIn(i, h1) if(i != toDel1) tmp.pb(i);
        swap(tmp, h1);
        tmp.clear();
        repIn(i, lh1) if(i != toDel1) tmp.pb(i);
        swap(tmp, lh1);
        tmp.clear();
        repIn(i, rh1) if(i != toDel1) tmp.pb(i);
        swap(tmp, rh1);
        tmp.clear();
        repIn(i, h2) if(i != toDel2) tmp.pb(i);
        swap(tmp, h2);
        tmp.clear();
    }

    sz = h1.size();
    if(sz == 0) return;
    if(sz == 1) { Answer(h1.back() + 1, h2.back() + 1); return; }

    repIn(i, h2) {
        if(lh2.size() == lh1.size()) { rh2.pb(i); continue; }
        if(rh2.size() == rh1.size()) { lh2.pb(i); continue; }
        auto newPairs = myQuery(i);
        if(newPairs != curPairs) lh2.pb(i);
        else rh2.pb(i);
        curPairs = newPairs;
    }
    dq(lh1, lh2, true);
    dq(rh1, rh2, false);
}

void Solve(int N) {
    n = N;
    vector<int> firstHalf, secondHalf;
    rep(i, 0, 2 * N) {
        if((int)firstHalf.size() == n) { secondHalf.pb(i); continue; }
        if((int)secondHalf.size() == n) { firstHalf.pb(i), curPairs = myQuery(i); continue; }
        auto newPairs = myQuery(i);
        if(newPairs != curPairs) secondHalf.pb(i);
        else firstHalf.pb(i);
        curPairs = newPairs;
        if(firstHalf.size() == secondHalf.size()) dq(firstHalf, secondHalf, 1), n -= firstHalf.size(), firstHalf.clear(), secondHalf.clear();
    }
    dq(firstHalf, secondHalf, 1);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10