Submission #1068883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068883		_8_8_	Chameleon's Love (JOI20_chameleon)	C++17	44 / 100	46 ms	860 KiB

chameleon

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

const int N = 5e3 + 12;
vector<int> g[N];
int n;
vector<int> f;
void make(vector<int> &l,vector<int> &r,int i) {
    l.clear();
    r.clear();
    vector<int> d(N,0);
    function<void(int)>dfs = [&](int v) {
        if(d[v] & 1) {
            l.push_back(v);
        } else {
            r.push_back(v);
        }
        for(int to:g[v]) {
            if(!d[to]) {
                d[to] = d[v] + 1;
                dfs(to);
            }
        }
    };
    for(int k = 0;k < i;k++) {
        int j = f[k];
        if(!d[j]) {
            d[j] = 1;
            dfs(j);
        }
    }
}
bool vis[N];
int to[N],fr[N];
set<int> st[N];
mt19937 rng(12321);
void Solve(int n_) {
    n = n_;
    vector<int> l,r;
    f.resize(n + n);
    iota(f.begin(),f.end(),1);
    shuffle(f.begin(),f.end(),rng);
    for(int _ = 1; _ < (int)f.size(); _++) {
        int i = f[_];
        make(l,r,_);
        auto ed = [&](vector<int> &x) -> void{
            int it = 0,m = (int)x.size();
            while(it < m) {
                if((int)g[i].size() == 3) break;
                int l = it - 1,r = m;
                while(r - l > 1) {
                    int mid = (l + r) >> 1;
                    vector<int> t(1,i);
                    for(int j = it; j <= mid; ++j) {
                        t.push_back(x[j]);
                    }
                    if(Query(t) != (int)t.size()) {
                        r = mid; 
                    } else {
                        l = mid;
                    }
                }
                if(r != m) {
                    g[i].push_back(x[r]);
                    g[x[r]].push_back(i);
                }
                if((int)g[i].size() == 3) break;
                it = r + 1;
            }
        };
        ed(l);
        ed(r);
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        if(g[i].size() == 1) {
            Answer(i,g[i][0]);
            vis[i] = vis[g[i][0]] = 1;
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        for(int j:g[i]) {
            if(vis[j]) continue;
            st[i].insert(j);
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        if((int)st[i].size() == 1) continue;
        if((int)g[i].size() >= 2 &&Query({i,g[i][0],g[i][1]}) == 1) {
            st[i].erase(g[i][2]);
            st[g[i][2]].erase(i);
        } else if(g[i].size() >= 3 && Query({i,g[i][2],g[i][1]}) == 1) {
            st[i].erase(g[i][0]);
            st[g[i][0]].erase(i);
        } else if(g[i].size() >= 3 && Query({i,g[i][0],g[i][2]}) == 1){
            st[i].erase(g[i][1]);
            st[g[i][1]].erase(i);
        }
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i] || st[i].empty()) continue;
        int t = (*st[i].begin());
        Answer(i,t);
        vis[i] = vis[t] = 1;
    }
}

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