Submission #430796

#	Time	Username	Problem	Language	Result	Execution time	Memory
430796		fivefourthreeone	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	77 ms	512 KiB

chameleon

    #pragma GCC target ("avx2")
    #pragma GCC optimize ("O3")
    #pragma GCC optimize ("unroll-loops")
    #include "chameleon.h"
    #include <bits/stdc++.h>
    #define owo(i,a, b) for(int i=(a);i<(b); ++i)
    #define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
    #define senpai push_back
    #define ttgl pair<int, int>
    #define ayaya cout<<"ayaya~"<<endl
     
    using namespace std;
    using ll = long long;
    using ld = long double;
    const ll MOD = 1000000007;
    const ll root = 3;
    ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
    ll modInv(ll a){return binpow(a, MOD-2);}
    const int INF = 0x3f3f3f3f;
    const int NINF = 0xc0c0c0c0;
    const ll INFLL = 0x3f3f3f3f3f3f3f3f;
    const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
    const int mxN = 1001;
    int type[mxN], col[mxN], nxt[mxN];
    /*void Answer(int a, int b) {
        if(col[a]^col[b]) {
            cout<<a<<" "<<b<<" you suck!\n";
            exit(0);
        }
    }*/
    int query(vector<int> &p) {
        return Query(p);
        /*set<int> colors;
        vector<bool> here(mxN, 0);
        for(int k: p) {
            here[k] = 1;
        }
        for(int k: p) {
            if(here[nxt[k]])colors.insert(col[nxt[k]]);
            else colors.insert(col[k]);
        }
        return colors.size();*/
    }
    vector<int> getrange(int a, int b, vector<int> &c, int d) {
        if(a > b)return {};
        vector<int> q;
        owo(i, a, b+1) {
            q.senpai(c[i]);
        }
        int l = a;
        int r = b;
        q.senpai(d);
        if(query(q) > b-a+1)return {};
        while(l < r) {
            q.clear();
            int m = (l + r) >> 1;
            owo(i, a, m+1) {
                q.senpai(c[i]);
            }
            q.senpai(d);
            if(query(q)<=m-a+1)r = m;
            else l = m + 1;
        }
        vector<int> res = getrange(l+1, b, c, d);
        res.senpai(c[l]);
        return res;
    }
    vector<int> adj[mxN];
    void bipartite(int n, vector<int> &l, vector<int> &r) {
        vector<int> col(n+1, -1);
        owo(i, 1, n+1) {
            if(col[i]!=-1)continue;
            queue<int> q;
            q.push(i);
            col[i] = 0;
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(int v: adj[u]) {
                    if(col[v]==-1) {
                        col[v] = col[u]^1;
                        q.push(v);
                    }
                }
            }
        }
        owo(i, 1, n+1) {
            if(col[i])r.senpai(i);
            else l.senpai(i);
        }
    }
    void Solve(int n) {
        vector<bool> done(2*n+1);
        vector<int> point(2*n+1);
        owo(i, 2, 2*n+1) {
            vector<int> l, r;
            bipartite(i-1, l, r);
            vector<int> edges = getrange(0, l.size()-1, l, i);
            for(int k: edges) {
                adj[k].senpai(i);
                adj[i].senpai(k);
            }
            edges = getrange(0, r.size()-1, r, i);
            for(int k: edges) {
                adj[k].senpai(i);
                adj[i].senpai(k);
            }
        }
        owo(i, 1, 2*n+1) {
            if(adj[i].size()==1 && !done[i]) {
                Answer(i, adj[i][0]);
                done[adj[i][0]] = 1;
            }else if(adj[i].size()==3) {
                vector<int> q = {i, adj[i][0], adj[i][1]};
                if(query(q)==1) {
                    point[i] = adj[i][2];
                }else {
                    q = {i, adj[i][0], adj[i][2]};
                    if(query(q)==1) {
                        point[i] = adj[i][1];
                    }else {
                        point[i] = adj[i][0];
                    }
                }
            }
        }
        owo(i, 1, 2*n+1) {
            if(adj[i].size()==3) {
                int o = point[i];
                if(done[o])continue;
                int sam = i^adj[o][0]^adj[o][1]^adj[o][2]^point[o];
                Answer(o, sam);
                done[o] = 1;
                done[sam] = 1;
            }
        }
    }
    /*int main() {
        //freopen("file.in", "r", stdin);
        //freopen("file.out", "w", stdout);
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        cin.tie(0)->sync_with_stdio(0);
        int T = 1;
        int n;
        for(int tc = 1; tc <= T; tc++) {
            cin>>n;
            owo(i, 1, 2*n+1) {
                cin>>type[i];
            }
            owo(i, 1, 2*n+1) {
                cin>>col[i];
            }
            owo(i, 1, 2*n+1) {
                cin>>nxt[i];
            }
            Solve(n);
        }
        return 0;
    }*/

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