Submission #533164

#	Time	Username	Problem	Language	Result	Execution time	Memory
533164		balbit	Chameleon's Love (JOI20_chameleon)	C++14	44 / 100	39 ms	404 KiB

chameleon

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

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#ifdef BALBIT
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


namespace {
const int maxn = 1000+3;
//int variable_example = 1;

vector<int> g[maxn]; // currently known graph
vector<int> p0, p1; // parts of bipartite graph

int col[maxn];

void bpdfs(int v, int c) {
    col[v] = c;
    for (int u : g[v]) {
        if (col[u] == -1) {
            bpdfs(u, c^1);
        }
    }
}

int QQ(vector<int> x) {
    for (int &y : x) ++y;
    return Query(x);
}

bool add(vector<int> &p, int v, int l, int r, bool def) {
    if (l > r) return 0;
    if (def == 0) {
        vector<int> aa;
        for (int i = l; i<=r; ++i) aa.pb(p[i]);
        aa.pb(v);
        int gt = QQ(aa);
        if (gt < SZ(aa) ) {
            // there is a love pair or an orig color pair
            def = 1;
        }
    }

    if (!def) return 0;
    if (l == r) {
        //here!
        int u = p[l];
        g[u].pb(v); g[v].pb(u);
        return 1;
    }
    int mid = (l+r)/2;
    bool getleft = add(p, v, l, mid, 0);
    add(p, v, mid+1, r, !getleft); // if getleft found nothing, there has to be smth in the right
    return 1;
}

set<pii> ban;

void bye(int a, int b) {
    if (a > b) swap(a,b);
    ban.insert({a,b});
}
}  // namespace



void Solve(int n) {
    REP(i, 2*n) {
        memset(col, -1, sizeof col);
        p0.clear(); p1.clear();
        REP(j, i) {
            if (col[j] == -1) {
                bpdfs(j, 0);
            }
        }
        REP(j,i) {
            (col[j]?p1:p0).pb(j);
        }
        add(p0, i, 0, SZ(p0)-1, 0);
        add(p1, i, 0, SZ(p1)-1, 0);
    }

//    REP(i,n*2) {
//        for (int v : g[i]) {
//            bug(i+1, v+1);
//        }
//    }

    REP(i,n*2) {
        if (SZ(g[i]) == 1) continue;
        assert(SZ(g[i]) <= 3);
        int no2 = QQ({i, g[i][0], g[i][1]});
        if (no2 == 1) {
            bye(i, g[i][2]); continue;
        }
        int no1 = QQ({i, g[i][0], g[i][2]});
        if (no1 == 1) {
            bye(i, g[i][1]); continue;
        }
        bye(i, g[i][0]);
    }
    vector<pii> re;
    REP(i,n*2) {
        for (int u : g[i]) {
            if (u < i && !ban.count({u,i})) {
                re.pb({u,i});
                bug(u+1, i+1);
            }
        }
    }
    for (pii p : re) {
        Answer(p.f+1, p.s+1);
    }
}





/*
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
*/

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36