Submission #64949242

---

Source Code Expand

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

/*--------------------------------------------------------------*/
/*                     Morton‑(Z‑order) код                     */
/*--------------------------------------------------------------*/
static inline uint32_t interleaveBits(uint16_t x) {
    uint32_t v = x;
    v = (v | (v << 8)) & 0x00FF00FF;
    v = (v | (v << 4)) & 0x0F0F0F0F;
    v = (v | (v << 2)) & 0x33333333;
    v = (v | (v << 1)) & 0x55555555;
    return v;
}
static inline uint32_t morton(uint16_t x, uint16_t y) {
    return (interleaveBits(y) << 1) | interleaveBits(x);
}

/*--------------------------------------------------------------*/
/*                 Аппроксимационный Prim (O(g²))               */
/*--------------------------------------------------------------*/
vector<pair<int,int>> approximateMST(const vector<int>& v,
                                     const vector<int>& cx,
                                     const vector<int>& cy)
{
    const int g = (int)v.size();
    const long long INF = (1LL<<60);
    vector<long long> best(g, INF);
    vector<int> parent(g, -1);
    vector<char> used(g, 0);
    best[0] = 0;
    vector<pair<int,int>> edges;

    for (int step = 0; step < g; ++step) {
        int u = -1;
        long long b = INF;
        for (int i = 0; i < g; ++i)
            if (!used[i] && best[i] < b) { b = best[i]; u = i; }
        used[u] = 1;
        if (parent[u] != -1)
            edges.emplace_back(v[u], v[parent[u]]);

        for (int i = 0; i < g; ++i) if (!used[i]) {
            long long dx = cx[v[u]] - cx[v[i]];
            long long dy = cy[v[u]] - cy[v[i]];
            long long d2 = dx*dx + dy*dy;
            if (d2 < best[i]) { best[i] = d2; parent[i] = u; }
        }
    }
    return edges;            // g‑1 рёбер
}

/*--------------------------------------------------------------*/
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* ---------- чтение входа ---------- */
    int N,M,Q,L,W;
    if(!(cin>>N>>M>>Q>>L>>W)) return 0;

    vector<int> G(M);
    for(int &g:G) cin>>g;

    vector<int> lx(N),rx(N),ly(N),ry(N);
    for(int i=0;i<N;++i) cin>>lx[i]>>rx[i]>>ly[i]>>ry[i];

    /* ---------- оценка координат и Morton‑сортировка ---------- */
    vector<int> cx(N), cy(N);      // центры
    vector<uint32_t> code(N);      // Z‑order код
    for(int i=0;i<N;++i){
        cx[i]=(lx[i]+rx[i])>>1;
        cy[i]=(ly[i]+ry[i])>>1;
        code[i]=morton((uint16_t)cx[i],(uint16_t)cy[i]);
    }
    vector<int> order(N);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),
         [&](int a,int b){ return code[a]<code[b]; });

    /* ---------- делим города на группы ---------- */
    vector<vector<int>> groups;
    groups.reserve(M);
    int ptr=0;
    for(int g:G){
        groups.emplace_back(order.begin()+ptr, order.begin()+ptr+g);
        ptr+=g;
    }

    /* ---------- основная часть: запросы / MST ---------- */
    int queriesUsed = 0;
    vector<vector<pair<int,int>>> edges(M);

    for(int k=0;k<M;++k){
        const auto& grp = groups[k];
        int gsz = (int)grp.size();
        /* --- попробуем получить идеальные рёбра через гадалку --- */
        if(gsz>=2 && gsz<=L && queriesUsed < Q){
            ++queriesUsed;
            cout << "? " << gsz;
            for(int id:grp) cout << ' ' << id;
            cout << endl;         // обязательно \n  + flush (endl flush’ит)
            /* получаем gsz-1 строк пар (u v) */
            for(int i=0;i<gsz-1;++i){
                int a,b; cin>>a>>b;
                edges[k].emplace_back(a,b);
            }
        }else if(gsz>=2){
            /* --- fallback: приблизительный Prim по центрам --- */
            edges[k] = approximateMST(grp,cx,cy);
        }
        /* если gsz==1 — рёбра не нужны */
    }

    /* ---------- вывод окончательного решения ---------- */
    cout << "!\n";
    for(int k=0;k<M;++k){
        const auto& grp = groups[k];
        for(size_t i=0;i<grp.size();++i){
            if(i) cout << ' ';
            cout << grp[i];
        }
        cout << '\n';
        for(auto [u,v] : edges[k])
            cout << u << ' ' << v << '\n';
    }
    cout.flush();
    return 0;
}

Submission Info

Judge Result