Submission #919402

#	Time	Username	Problem	Language	Result	Execution time	Memory
919402		winter0101	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	40 ms	1620 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
mt19937_64 rng(310197);
const int maxn = 1e3 + 9;
vector<int>a[maxn];
bool edg[maxn][maxn];
bool vis[maxn];
bool type[maxn];
void dfs(int u) {
    for (auto v : a[u]) {
        if (vis[v])
            continue;

        type[v] = (type[u] ^ 1);
        vis[v] = 1;
        dfs(v);
    }
}
void Solve(int n) {
    vector<int>white, black;
    for2(i, 2 * n, 1) {
        if (white.empty() && black.empty()) {
            white.pb(i);
            continue;
        }

        if (1) {
            int lst = -1;

            while (true) {
                int l = lst + 1, r = sz(white) - 1, ans = -1;
                vector<int>ck = {i};
                for1(j, lst + 1, r)ck.pb(white[j]);

                if (Query(ck) == sz(ck))
                    break;

                while (l <= r) {
                    int mid = (l + r) / 2;
                    vector<int>check;
                    for1(j, lst + 1, mid) {
                        check.pb(white[j]);
                    }
                    check.pb(i);

                    if (sz(check) > Query(check)) {
                        ans = mid;
                        r = mid - 1;
                    } else
                        l = mid + 1;
                }

                if (ans == -1)
                    break;

                lst = ans;
                a[i].pb(white[ans]);
                a[white[ans]].pb(i);
                //cout<<i<<" "<<white[ans]<<'\n';
            }
        }

        swap(black, white);

        if (1) {
            int lst = -1;

            while (true) {
                int l = lst + 1, r = sz(white) - 1, ans = -1;
                vector<int>ck = {i};
                for1(j, lst + 1, r)ck.pb(white[j]);

                if (Query(ck) == sz(ck))
                    break;

                while (l <= r) {
                    int mid = (l + r) / 2;
                    vector<int>check;
                    for1(j, lst + 1, mid) {
                        check.pb(white[j]);
                    }
                    check.pb(i);

                    if (sz(check) > Query(check)) {
                        ans = mid;
                        r = mid - 1;
                    } else
                        l = mid + 1;
                }

                if (ans == -1)
                    break;

                lst = ans;
                a[i].pb(white[ans]);
                a[white[ans]].pb(i);
                //cout<<i<<" "<<white[ans]<<'\n';
            }
        }

        white.clear();
        black.clear();
        for1(j, i, 2 * n) {
            vis[j] = 0;
        }
        for1(j, i, 2 * n) {
            if (!vis[j]) {
                vis[j] = 1;
                type[j] = 0;
                dfs(j);
            }
        }
        for1(j, i, 2 * n) {
            if (!type[j])
                white.pb(j);
            else
                black.pb(j);
        }
    }
    //cout<<"ya";
    vector<pii>ans;
    for1(i, 1, 2 * n) {
        if (sz(a[i]) == 1) {
            for (auto v : a[i]) {
                //cout<<i<<" "<<v<<'\n';
                edg[v][i] = edg[i][v] = 1;
            }
        } else {
            vector<int>check;
            check.pb(i);
            for1(j, 0, sz(a[i]) - 1) {
                check.pb(a[i][j]);
                for1(k, j + 1, sz(a[i]) - 1) {
                    check.pb(a[i][k]);

                    if (Query(check) == 1) {
                        edg[i][a[i][j]] = 1;
                        edg[i][a[i][k]] = 1;
                    }

                    check.pop_back();
                }
                check.pop_back();
            }
        }
    }
    for1(i, 1, 2 * n) {
        for1(j, i + 1, 2 * n) {
            if (edg[i][j] && edg[j][i]) {
                Answer(i, j);
            }
        }
    }
}

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