Submission #1068805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068805		_8_8_	Chameleon's Love (JOI20_chameleon)	C++17	4 / 100	48 ms	624 KiB

chameleon

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

const int N = 5e3 + 12;
vector<int> g[N];
int n;
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 j = 1;j < i;j++) {
        if(!d[j]) {
            d[j] = 1;
            dfs(j);
        }
    }
}
bool vis[N];
void Solve(int n_) {
    n = n_;
    vector<int> l,r;
    for(int i = 2;i <= n + n;i++) {
        make(l,r,i);
        auto ed = [&](vector<int> &x) -> void{
            int it = 0,m = (int)x.size();
            while(it < m) {
                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);
                }
                it = r + 1;
            }
        };
        ed(l);
        ed(r);
        // return; 
    }
    for(int i = 1;i <= n + n;i++) {
        if(vis[i]) continue;
        Answer(i,g[i][0]);
        vis[g[i][0]] = 1;
    }
}

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