提出 #66999739

---

ソースコード 拡げる

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

int Query(const vector<int> &p);
void Answer(int a, int b);

namespace solution {

const int N = 1005;
int g[N][N];

vector<int> join(vector<int> a, int b){ return a.push_back(b), a; }

int find(const vector<int>& p, int x){
    int l = 0, r = p.size() - 1;
    assert(p.size());
    while(l < r){
        int mid = (l + r) >> 1;
        vector<int> vct(p.begin(), p.begin() + mid + 1);
        if(Query(join(vct, x)) == (int)vct.size() + 1) l = mid + 1;
        else r = mid;
    }
    return p[l];
}

void Solve(int n){
    vector<int> proc(n << 1);
    iota(proc.begin(), proc.end(), 1);
    while(!proc.empty()){
        vector<int> ind, nind;
        for(int i : proc) (Query(join(ind, i)) == (int)ind.size() + 1 ? ind : nind).push_back(i);
        for(int u : nind){
            vector<int> S = ind;
            while(Query(join(S, u)) != (int)S.size() + 1){
                int v = find(S, u); g[u][v] = g[v][u] = 1;
                S.erase(find(S.begin(), S.end(), v));
            }
        }
        proc = nind;
    }
    for(int i=1;i<=(n<<1);i++){
        int ngb[3], t = 0;
        for(int j=1;j<=(n<<1);j++) if(g[i][j]) ngb[t++] = j;
        if(t == 1) continue;
        auto query = [&](int x, int y, int z){
            if(Query({i, x, y}) == 1) return g[i][z] = g[z][i] = 2, 0;
            return 1;
        };
        auto [x, y, z] = ngb;
        if(query(x, y, z)) if(query(x, z, y)) g[i][x] = g[x][i] = 2;
    }
    for(int i=1;i<=(n<<1);i++){
        for(int j=1;j<i;j++) if(g[i][j] == 1) Answer(i, j);
    }
}

}

void Solve(int n){ solution::Solve(n); }

// Written by xiezheyuan

提出情報

ジャッジ結果