answer.cpp

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

// ── ThreadPool ────────────────────────────────────────────────────────────────
class ThreadPool {
private:
    vector<thread> workers;
    queue<function<void()>> tasks;
    mutable mutex queue_mutex;
    condition_variable condition;
    atomic<bool> stop_flag;

public:
    explicit ThreadPool(size_t threads = 1) : stop_flag(false) {
        for (size_t i = 0; i < threads; ++i) {
            workers.emplace_back([this] {
                while (true) {
                    function<void()> task;
                    {
                        unique_lock<mutex> lock(queue_mutex);
                        condition.wait(lock, [this] { return stop_flag || !tasks.empty(); });
                        if (stop_flag && tasks.empty()) return;
                        task = move(tasks.front());
                        tasks.pop();
                    }
                    task();
                }
            });
        }
    }

    template<class F, class... Args>
    auto enqueue(F&& f, Args&&... args) -> future<typename invoke_result<F, Args...>::type> {
        using R = typename invoke_result<F, Args...>::type;
        auto task = make_shared<packaged_task<R()>>(bind(forward<F>(f), forward<Args>(args)...));
        future<R> res = task->get_future();
        {
            unique_lock<mutex> lock(queue_mutex);
            if (stop_flag) throw runtime_error("ThreadPool stopped");
            tasks.emplace([task]() { (*task)(); });
        }
        condition.notify_one();
        return res;
    }

    ~ThreadPool() {
        { unique_lock<mutex> lock(queue_mutex); stop_flag = true; }
        condition.notify_all();
        for (auto& w : workers) w.join();
    }
};

// ── Constants ────────────────────────────────────────────────────────────────
static const int MAX_W = 64;
static const int MAX_H = 40;
static const int GRID  = MAX_W * MAX_H; // 2560
static const int INF   = 1e9;
static const int TL_MS = 35;

static const int DX[4] = {0, 0, -1, 1};
static const int DY[4] = {-1, 1, 0, 0};
static const char* DNAME[4] = {"UP", "DOWN", "LEFT", "RIGHT"};

static int W, H;

// Rôles des serpents alliés
enum Role { COLLECTOR = 0, BLOCKER = 1, KILLER = 2 };

inline void bsSet(bitset<2560>& bs, int pos) {
    if (pos >= 0 && pos < 2560) bs.set(pos);
}
inline int  enc(int x, int y)      { return y * MAX_W + x; }
inline int  ex(int e)              { return e % MAX_W; }
inline int  ey(int e)              { return e / MAX_W; }
inline bool inBounds(int x, int y) { return x >= 0 && x < W && y >= 0 && y < H; }

// ── Snake ────────────────────────────────────────────────────────────────────
struct Snake {
    int  id     = -1;
    vector<int> body;
    bool alive  = true;
    Role role   = COLLECTOR;

    int  head()    const { return body[0]; }
    int  length()  const { return (int)body.size(); }
    bool isShort() const { return length() <= 4; }
};

// ── Globals ───────────────────────────────────────────────────────────────────
static bitset<2560> g_platforms;
static vector<int>  g_myIds, g_oppIds;
static atomic<bool> g_timeout{false};

// ── Obstacle builders ─────────────────────────────────────────────────────────
bitset<2560> buildObstacles(const Snake& snake, const unordered_map<int,Snake>& all) {
    bitset<2560> obs = g_platforms;
    // Own body excluding tail (tail will vacate next turn)
    for (int i = 1; i < (int)snake.body.size()-1; i++) bsSet(obs, snake.body[i]);
    // Full opponent bodies
    for (int oid : g_oppIds)
        if (all.count(oid)) for (int c : all.at(oid).body) bsSet(obs, c);
    // Allied bodies excluding their tails — prevents friendly collisions
    for (int aid : g_myIds) {
        if (aid == snake.id || !all.count(aid)) continue;
        const auto& ally = all.at(aid);
        for (int i = 0; i < (int)ally.body.size()-1; i++) bsSet(obs, ally.body[i]);
    }
    return obs;
}

bitset<2560> allOtherBodies(const Snake& snake, const unordered_map<int,Snake>& all) {
    bitset<2560> bodies;
    for (auto& [id,s] : all)
        if (id != snake.id) for (int c : s.body) bsSet(bodies, c);
    return bodies;
}

// ── Flood fill ────────────────────────────────────────────────────────────────
int floodFill(int start, const bitset<2560>& obs, int limit = 50) {
    if (obs[start]) return 0;
    queue<int> q;
    bitset<2560> visited;
    q.push(start); visited.set(start);
    int count = 0;
    while (!q.empty() && count < limit) {
        int c = q.front(); q.pop();
        count++;
        int x = ex(c), y = ey(c);
        for (int d = 0; d < 4; d++) {
            int nx = x+DX[d], ny = y+DY[d];
            if (!inBounds(nx,ny)) continue;
            int nc = enc(nx,ny);
            if (obs[nc] || visited[nc]) continue;
            visited.set(nc); q.push(nc);
        }
    }
    return count;
}

// ── Safety ────────────────────────────────────────────────────────────────────
bool isSafe(int pos, const Snake& snake, const bitset<2560>& obs,
            const bitset<2560>& others, bool isEnergyTarget = false) {
    if (snake.isShort() && others[pos]) return false;
    if (isEnergyTarget) return true;
    if (floodFill(pos, obs, 20) < 5) return false;
    return true;
}

// ── BFS to targets ────────────────────────────────────────────────────────────
int bfsToTargets(const Snake& snake, const bitset<2560>& targets,
                 const bitset<2560>& obs, const bitset<2560>& others,
                 int* outTarget = nullptr) {
    if (targets.none()) return -1;
    int start = snake.head();
    queue<pair<int,int>> q;
    bitset<2560> visited;
    vector<int> firstDir(2560, -1);
    visited.set(start);
    int x0 = ex(start), y0 = ey(start);
    for (int d = 0; d < 4; d++) {
        int nx = x0+DX[d], ny = y0+DY[d];
        if (!inBounds(nx,ny)) continue;
        int nc = enc(nx,ny);
        if (obs[nc] || visited[nc]) continue;
        if (!isSafe(nc, snake, obs, others)) continue;
        visited.set(nc); firstDir[nc] = d; q.push({nc,d});
    }
    while (!q.empty()) {
        auto [c,fd] = q.front(); q.pop();
        if (targets[c]) { if (outTarget) *outTarget = c; return fd; }
        int x = ex(c), y = ey(c);
        for (int d = 0; d < 4; d++) {
            int nx = x+DX[d], ny = y+DY[d];
            if (!inBounds(nx,ny)) continue;
            int nc = enc(nx,ny);
            if (obs[nc] || visited[nc]) continue;
            visited.set(nc); firstDir[nc] = fd; q.push({nc,fd});
        }
    }
    return -1;
}

// ── Best open direction ───────────────────────────────────────────────────────
int bestOpen(const Snake& snake, const bitset<2560>& obs,
             const bitset<2560>& others, bool ignoreSafety = false) {
    int bestDir = -1, bestScore = -1;
    int x0 = ex(snake.head()), y0 = ey(snake.head());
    for (int d = 0; d < 4; d++) {
        int nx = x0+DX[d], ny = y0+DY[d];
        if (!inBounds(nx,ny)) continue;
        int nc = enc(nx,ny);
        if (obs[nc]) continue;
        int score = floodFill(nc, obs, 20);
        if (!ignoreSafety && !isSafe(nc, snake, obs, others)) score /= 4;
        if (score > bestScore) { bestScore = score; bestDir = d; }
    }
    return bestDir;
}

// ── Voronoi ───────────────────────────────────────────────────────────────────
pair<int,int> voronoi(const vector<int>& myH, const vector<int>& oppH,
                       const bitset<2560>& obs) {
    vector<uint8_t> owner(2560, 255);
    vector<int>     dist(2560, -1);
    queue<tuple<int,int,int>> q;
    for (int h : myH) if (!obs[h] && owner[h]==255)
        { owner[h]=0; dist[h]=0; q.push({h,0,0}); }
    for (int h : oppH) if (!obs[h]) {
        if (owner[h]==0) owner[h]=2;
        else if (owner[h]==255) { owner[h]=1; dist[h]=0; q.push({h,0,1}); }
    }
    while (!q.empty()) {
        auto [c,d,o] = q.front(); q.pop();
        if (dist[c] >= 0 && dist[c] < d) continue;
        int x = ex(c), y = ey(c);
        for (int dir = 0; dir < 4; dir++) {
            int nx = x+DX[dir], ny = y+DY[dir];
            if (!inBounds(nx,ny)) continue;
            int nc = enc(nx,ny);
            if (obs[nc]) continue;
            if (owner[nc]==255) {
                owner[nc]=o; dist[nc]=d+1; q.push({nc,d+1,o});
            } else if (dist[nc]==d+1 && owner[nc]!=o && owner[nc]!=2) {
                owner[nc]=2;
            }
        }
    }
    int m=0, op=0;
    for (int i=0; i<2560; i++) { if (owner[i]==0) m++; else if (owner[i]==1) op++; }
    return {m, op};
}

// ── BFS from head — returns dist[cell], -1 = unreachable ─────────────────────
vector<int> bfsFromHead(int start, const bitset<2560>& obs, int limit) {
    vector<int> dist(2560, -1);
    queue<pair<int,int>> q;
    dist[start] = 0; q.push({start,0});
    while (!q.empty()) {
        auto [c,d] = q.front(); q.pop();
        if (d >= limit) continue;
        int x = ex(c), y = ey(c);
        for (int di = 0; di < 4; di++) {
            int nx = x+DX[di], ny = y+DY[di];
            if (!inBounds(nx,ny)) continue;
            int nc = enc(nx,ny);
            if (obs[nc] || dist[nc] >= 0) continue;
            dist[nc] = d+1; q.push({nc,d+1});
        }
    }
    return dist;
}

// ── Evaluate ──────────────────────────────────────────────────────────────────
int evaluate(const vector<Snake>& myS, const vector<Snake>& oppS,
             const bitset<2560>& energy) {
    vector<const Snake*> am, ao;
    for (auto& s : myS)  if (s.alive) am.push_back(&s);
    for (auto& s : oppS) if (s.alive) ao.push_back(&s);
    if (am.empty()) return -INF;
    if (ao.empty()) return  INF;

    bitset<2560> obs = g_platforms;
    for (auto s : am) for (int c : s->body) bsSet(obs, c);
    for (auto s : ao) for (int c : s->body) bsSet(obs, c);

    vector<int> mh, oh;
    for (auto s : am) mh.push_back(s->head());
    for (auto s : ao) oh.push_back(s->head());
    auto [mc,oc] = voronoi(mh, oh, obs);

    int ml=0, ol=0;
    for (auto s : am) ml += s->length();
    for (auto s : ao) ol += s->length();

    // Energy bonus: one BFS per head (O(N_snakes × REACH²))
    const int REACH = 8;
    vector<vector<int>> myDists, oppDists;
    for (auto s : am)  myDists.push_back(bfsFromHead(s->head(), obs, REACH));
    for (auto o : ao)  oppDists.push_back(bfsFromHead(o->head(), obs, REACH));

    int eb=0, oppEb=0;
    for (int e=0; e<2560; e++) {
        if (!energy[e]) continue;
        int myBest=INT_MAX;
        for (auto& dm : myDists)  if (dm[e]>=0 && dm[e]<myBest)  myBest=dm[e];
        int oppBest=INT_MAX;
        for (auto& dm : oppDists) if (dm[e]>=0 && dm[e]<oppBest) oppBest=dm[e];
        if (myBest < INT_MAX) {
            if (myBest < oppBest)       eb += (REACH+1-myBest)*2;
            else if (myBest == oppBest) eb += (REACH+1-myBest);
        }
        if (oppBest < INT_MAX && oppBest < myBest) oppEb += (REACH+1-oppBest);
    }

    // Mobility penalty
    int mobility=0;
    for (auto s : am) {
        int space = floodFill(s->head(), obs, 20);
        if (space < 5)  mobility -= 15;
        else if (space < 10) mobility -= 5;
    }

    // Head collision danger (normal mode) / head proximity bonus (killer mode)
    int headDanger=0;
    bool scarceEnergy = ((int)energy.count() <= (int)(am.size() + ao.size()));
    for (auto s : am)
        for (auto o : ao) {
            int d = abs(ex(s->head())-ex(o->head())) + abs(ey(s->head())-ey(o->head()));
            if (scarceEnergy) {
                // Killer mode heuristic: reward closing in on opp heads
                // Safe to approach only if we're longer
                if (s->length() > o->length()) {
                    // Bonus for being close (max at d=1, decreases with distance)
                    if (d <= 5) headDanger += max(0, 6-d) * 4;
                } else {
                    // Still penalize head-on if we're shorter/equal
                    if (d <= 2) headDanger -= (o->length() >= s->length()) ? 20 : 5;
                }
            } else {
                if (d <= 2) headDanger -= (o->length() >= s->length()) ? 30 : 10;
            }
        }

    return (mc-oc)*3 + (ml-ol)*10 + eb - oppEb + mobility + headDanger;
}

// ── Gravity & sim ─────────────────────────────────────────────────────────────
void applyGravity(Snake& s, const bitset<2560>& obs, const bitset<2560>& energy) {
    if (!s.alive) return;
    while (true) {
        bool supported = false;
        for (int c : s.body) {
            int bx=ex(c), by=ey(c)+1;
            if (!inBounds(bx,by)) { supported=true; break; }
            int bc=enc(bx,by);
            if (obs[bc] || energy[bc]) { supported=true; break; }
        }
        if (supported) break;
        vector<int> newBody; bool fell_out=false;
        for (int c : s.body) {
            int nx=ex(c), ny=ey(c)+1;
            if (!inBounds(nx,ny)) { fell_out=true; break; }
            newBody.push_back(enc(nx,ny));
        }
        if (fell_out) { s.alive=false; return; }
        s.body = newBody;
    }
}

void simMove(Snake& s, int d, bitset<2560>& energy, const bitset<2560>& obs) {
    int nx=ex(s.head())+DX[d], ny=ey(s.head())+DY[d];
    if (!inBounds(nx,ny)) {
        if (s.length()<=3) s.alive=false;
        else s.body.erase(s.body.begin());
        return;
    }
    int nc=enc(nx,ny);
    if (obs[nc]) {
        if (s.length()<=3) s.alive=false;
        else s.body.erase(s.body.begin());
    } else if (energy[nc]) {
        s.body.insert(s.body.begin(), nc);
        energy.reset(nc);
    } else {
        s.body.insert(s.body.begin(), nc);
        s.body.pop_back();
    }
    if (s.alive) applyGravity(s, obs, energy);
}

// ── Move ordering ─────────────────────────────────────────────────────────────
vector<int> orderMoves(const Snake& snake, const bitset<2560>& obs,
                       const bitset<2560>& energy) {
    vector<pair<int,int>> scored;
    int x0=ex(snake.head()), y0=ey(snake.head());
    for (int d=0; d<4; d++) {
        int nx=x0+DX[d], ny=y0+DY[d];
        if (!inBounds(nx,ny)) continue;
        int nc=enc(nx,ny);
        if (obs[nc]) continue;
        int score = floodFill(nc, obs, 30);
        for (int e=0; e<2560; e++) {
            if (!energy[e]) continue;
            int dist = abs(ex(nc)-ex(e)) + abs(ey(nc)-ey(e));
            if (dist <= 3) score += max(0, 4-dist)*5;
        }
        scored.emplace_back(score, d);
    }
    sort(scored.begin(), scored.end(), [](auto& a, auto& b){ return a.first>b.first; });
    vector<int> dirs;
    for (auto& [s,d] : scored) dirs.push_back(d);
    return dirs;
}

// ── Minimax ───────────────────────────────────────────────────────────────────
struct MMR { int score; vector<int> dirs; };

MMR minimax(vector<Snake> myS, vector<Snake> oppS,
            bitset<2560> energy, int depth, int alpha, int beta, bool isMax) {
    if (g_timeout || depth==0) return {evaluate(myS,oppS,energy),{}};

    vector<int> ami, aoi;
    for (int i=0; i<(int)myS.size();  i++) if (myS[i].alive)  ami.push_back(i);
    for (int i=0; i<(int)oppS.size(); i++) if (oppS[i].alive) aoi.push_back(i);
    if (ami.empty()) return {-INF,{}};
    if (aoi.empty()) return { INF,{}};

    bitset<2560> obs = g_platforms;
    for (int i : ami) for (int j=1; j<(int)myS[i].body.size()-1; j++) bsSet(obs, myS[i].body[j]);
    for (int i : aoi) for (int c : oppS[i].body) bsSet(obs, c);

    if (isMax) {
        MMR best{-INF, vector<int>(ami.size(),0)};
        for (int si=0; si<(int)ami.size(); si++) {
            int bi=ami[si], bDir=0, bScore=-INF;
            auto orderedDirs = orderMoves(myS[bi], obs, energy);
            for (int d : orderedDirs) {
                if (g_timeout) break;
                vector<Snake> nm=myS; bitset<2560> ne=energy;
                simMove(nm[bi], d, ne, obs);
                auto r = minimax(nm, oppS, ne, depth-1, alpha, beta, false);
                if (r.score>bScore) { bScore=r.score; bDir=d; }
                alpha = max(alpha, r.score);
                if (beta<=alpha) break;
            }
            best.dirs[si]=bDir;
            best.score=max(best.score,bScore);
        }
        return best;
    } else {
        MMR best{INF,{}};
        for (int si : aoi) {
            auto orderedDirs = orderMoves(oppS[si], obs, energy);
            for (int d : orderedDirs) {
                if (g_timeout) break;
                vector<Snake> no=oppS; bitset<2560> ne=energy;
                simMove(no[si], d, ne, obs);
                auto r = minimax(myS, no, ne, depth-1, alpha, beta, true);
                best.score=min(best.score,r.score);
                beta=min(beta,r.score);
                if (beta<=alpha) break;
            }
        }
        return best;
    }
}

// ── Role assignment ───────────────────────────────────────────────────────────
// Appelée AVANT la boucle d'action. Attribue BLOCKER au serpent le plus proche
// d'un adversaire plus court que lui. Tous les autres sont COLLECTOR.
// Un seul BLOCKER max pour éviter que tout le monde cible le même ennemi.
void assignRoles(vector<Snake>& mySnakes, const unordered_map<int,Snake>& all) {
    for (auto& s : mySnakes) s.role = COLLECTOR;

    int blockerIdx = -1;
    int bestBlockDist = 4; // seuil Manhattan : n'intervient que si vraiment proche

    for (int si=0; si<(int)mySnakes.size(); si++) {
        auto& snake = mySnakes[si];
        for (int oid : g_oppIds) {
            if (!all.count(oid)) continue;
            const auto& opp = all.at(oid);
            // N'intercepte que si on est clairement plus long
            if (snake.length() <= opp.length() + 1) continue;
            int d = abs(ex(snake.head())-ex(opp.head()))
                  + abs(ey(snake.head())-ey(opp.head()));
            if (d < bestBlockDist) {
                bestBlockDist = d;
                blockerIdx = si;
            }
        }
    }
    if (blockerIdx >= 0) mySnakes[blockerIdx].role = BLOCKER;
}

// Pré-réserve une énergie par serpent COLLECTOR (Manhattan le plus proche).
// Retourne le bitset des énergies réservées (une par serpent max).
bitset<2560> preReserveEnergy(const vector<Snake>& mySnakes,
                               const bitset<2560>& energy) {
    bitset<2560> reserved;
    for (auto& snake : mySnakes) {
        if (snake.role != COLLECTOR) continue;
        int bestDist=INT_MAX, target=-1;
        int x0=ex(snake.head()), y0=ey(snake.head());
        for (int e=0; e<2560; e++) {
            if (!energy[e] || reserved[e]) continue;
            int d = abs(ex(e)-x0) + abs(ey(e)-y0);
            if (d < bestDist) { bestDist=d; target=e; }
        }
        if (target>=0) reserved.set(target);
    }
    return reserved;
}

// ── Main ──────────────────────────────────────────────────────────────────────
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int myId; cin >> myId >> W >> H;
    for (int y=0; y<H; y++) {
        string row; cin>>row;
        for (int x=0; x<(int)row.size(); x++)
            if (row[x]=='#') g_platforms.set(enc(x,y));
    }
    int sbpp; cin>>sbpp;
    vector<int> block0, block1;
    for (int i=0; i<sbpp; i++) { int id; cin>>id; block0.push_back(id); }
    for (int i=0; i<sbpp; i++) { int id; cin>>id; block1.push_back(id); }
    g_myIds  = block0;
    g_oppIds = block1;
    cerr << "DEBUG myId=" << myId << " myIds:";
    for (int id : g_myIds) cerr<<" "<<id;
    cerr << " oppIds:";
    for (int id : g_oppIds) cerr<<" "<<id;
    cerr << endl;

    unordered_map<int,deque<int>> headHist;
    int  noEnergyTurns = 0;  // tours consecutifs sans energie collectee
    int  prevTotalLen  = 0;  // longueur totale alliee au tour precedent
    bool killerMode    = false;
    static const int KILLER_TRIGGER = 8; // tours sans collect -> killer mode
    ThreadPool pool(1);

    while (true) {
        auto t0 = chrono::steady_clock::now();
        g_timeout = false;

        int pc; cin>>pc;
        bitset<2560> energy;
        for (int i=0; i<pc; i++) { int x,y; cin>>x>>y; energy.set(enc(x,y)); }

        int sc; cin>>sc;
        unordered_map<int,Snake> all;
        for (int i=0; i<sc; i++) {
            int sid; string bs; cin>>sid>>bs;
            Snake s; s.id=sid; s.alive=true;
            stringstream ss(bs); string seg;
            while (getline(ss,seg,':')) {
                int x,y;
                if (sscanf(seg.c_str(),"%d,%d",&x,&y)==2)
                    s.body.push_back(enc(x,y));
                else
                    cerr<<"DEBUG parse ERROR seg=["<<seg<<"]"<<endl;
            }
            if (s.body.empty())
                cerr<<"DEBUG WARNING: snake "<<sid<<" empty body, skipping"<<endl;
            else
                all[sid]=s;
        }

        vector<int> aliveM, aliveO;
        for (int id : g_myIds)  if (all.count(id)) aliveM.push_back(id);
        for (int id : g_oppIds) if (all.count(id)) aliveO.push_back(id);
        sort(aliveM.begin(), aliveM.end(), [&](int a, int b){
            return all[a].length() > all[b].length();
        });

        vector<Snake> mySnakes, oppSnakes;
        for (int id : aliveM)  mySnakes.push_back(all[id]);
        for (int id : aliveO)  oppSnakes.push_back(all[id]);

        // ── Killer mode detection ─────────────────────────────────────────────
        // On mesure si l'equipe a mange de l'energie ce tour
        int curTotalLen = 0;
        for (int id : aliveM) curTotalLen += all[id].length();

        if (curTotalLen > prevTotalLen && prevTotalLen > 0) {
            // De l'energie a ete collectee ce tour
            noEnergyTurns = 0;
            if (killerMode) {
                killerMode = false;
                cerr << "DEBUG killer mode OFF (energy collected)" << endl;
            }
        } else if (!energy.none()) {
            // De l'energie existe sur la grille mais personne n'en prend
            noEnergyTurns++;
        }
        prevTotalLen = curTotalLen;

        if (!killerMode && noEnergyTurns >= KILLER_TRIGGER) {
            killerMode = true;
            cerr << "DEBUG killer mode ON (noEnergyTurns=" << noEnergyTurns << ")" << endl;
        }
        cerr << "DEBUG killerMode=" << killerMode
             << " noEnergyTurns=" << noEnergyTurns
             << " totalLen=" << curTotalLen << endl;

        // ── Roles + pré-réservation d'énergie ────────────────────────────────
        if (killerMode) {
            for (auto& s : mySnakes) s.role = KILLER;
        } else {
            assignRoles(mySnakes, all);
        }
        bitset<2560> reserved = killerMode
            ? bitset<2560>{}
            : preReserveEnergy(mySnakes, energy);

        // Met à jour les rôles dans `all` pour que buildObstacles/etc. voient role
        for (auto& s : mySnakes) all[s.id].role = s.role;

        cerr << "DEBUG roles:";
        for (auto& s : mySnakes)
            cerr<<" "<<s.id<<"="<<(s.role==KILLER?"KIL":s.role==BLOCKER?"BLK":"COL");
        cerr << endl;

        // ── Depth dynamique ───────────────────────────────────────────────────
        int totalAlive = (int)(aliveM.size() + aliveO.size());
        int dynamicMaxDepth;
        if      (totalAlive <= 2) dynamicMaxDepth = 5;
        else if (totalAlive <= 4) dynamicMaxDepth = 4;
        else if (totalAlive <= 6) dynamicMaxDepth = 3;
        else                      dynamicMaxDepth = 2;
        cerr << "DEBUG alive=" << totalAlive << " maxDepth=" << dynamicMaxDepth << endl;

        // ── Minimax async ─────────────────────────────────────────────────────
        auto future = pool.enqueue([mySnakes, oppSnakes, energy, dynamicMaxDepth]() -> MMR {
            MMR best; best.score = -INF;
            for (int depth=2; depth<=dynamicMaxDepth && !g_timeout; depth++) {
                auto res = minimax(mySnakes, oppSnakes, energy, depth, -INF, INF, true);
                if (!res.dirs.empty()) {
                    best = res;
                    cerr << "DEBUG depth=" << depth << " score=" << res.score << endl;
                }
            }
            return best;
        });

        MMR mmResult;
        if (future.wait_for(chrono::milliseconds(TL_MS)) != future_status::ready) {
            g_timeout = true;
            if (future.wait_for(chrono::milliseconds(10)) == future_status::ready)
                mmResult = future.get();
            else
                cerr << "DEBUG WARNING: minimax timeout, using fallback" << endl;
        } else {
            mmResult = future.get();
        }
        vector<int> mmDirs = mmResult.dirs;

        // ── Génération des actions ────────────────────────────────────────────
        vector<string> actions, marks;

        for (int si=0; si<(int)aliveM.size(); si++) {
            int sid = aliveM[si];
            Snake& snake = all[sid];

            // Màj historique
            headHist[sid].push_back(snake.head());
            if ((int)headHist[sid].size()>4) headHist[sid].pop_front();

            // ── Détection stuck ───────────────────────────────────────────────
            bool stuck = false;
            {
                auto& h = headHist[sid];
                int n = (int)h.size();
                if (n>=3) {
                    if (h[0]==h[1] && h[1]==h[2])          stuck=true; // A-A-A
                    if (h[0]==h[2] && h[0]!=h[1])          stuck=true; // A-B-A
                }
                if (n>=4) {
                    if (h[0]==h[2] && h[1]==h[3] && h[0]!=h[1]) stuck=true; // A-B-A-B
                }
            }

            auto obs    = buildObstacles(snake, all);
            auto others = allOtherBodies(snake, all);
            int dir = -1;

            if (stuck) {
                cerr << "DEBUG " << sid << " stuck" << endl;
                // Priorité horizontale (corrige bounces gravité), respecte toujours les alliés
                for (int d : {2,3,0,1}) {
                    int nx=ex(snake.head())+DX[d], ny=ey(snake.head())+DY[d];
                    if (!inBounds(nx,ny)) continue;
                    if (obs[enc(nx,ny)]) continue;
                    dir=d; break;
                }
                if (dir<0) dir=bestOpen(snake,obs,others,false);
                // Dernier recours : ignore sa propre queue seulement
                if (dir<0) {
                    auto obsNoTail = obs;
                    if (!snake.body.empty()) obsNoTail.reset(snake.body.back());
                    for (int d : {2,3,0,1}) {
                        int nx=ex(snake.head())+DX[d], ny=ey(snake.head())+DY[d];
                        if (!inBounds(nx,ny)) continue;
                        if (obsNoTail[enc(nx,ny)]) continue;
                        dir=d; break;
                    }
                }
                headHist[sid].clear();

            } else {
                // ── 1. Minimax (décision principale) ─────────────────────────
                if (si<(int)mmDirs.size()) {
                    int md=mmDirs[si];
                    int nx=ex(snake.head())+DX[md], ny=ey(snake.head())+DY[md];
                    if (inBounds(nx,ny) && !obs[enc(nx,ny)]) dir=md;
                }

                // ── 2. Fallback rôle-dépendant si minimax n'a rien donné ─────
                if (dir<0) {
                    Role role = mySnakes[si].role;

                    if (role == KILLER) {
                        // En killer mode : cibler toutes les têtes adverses sans
                        // condition de longueur. On utilise un obs spécial qui
                        // exclut les corps alliés de la collision check pour éviter
                        // que les serpents ne se gênent entre eux, MAIS on garde
                        // les corps alliés comme obstacles (pas de suicide allié).
                        bitset<2560> oppHeads;
                        for (int oid : g_oppIds) {
                            if (!all.count(oid)) continue;
                            oppHeads.set(all.at(oid).head());
                        }
                        if (oppHeads.any()) {
                            // isSafe bypass : on accepte les zones étroites en killer mode
                            // mais on garde buildObstacles normal (alliés protégés)
                            dir = bfsToTargets(snake, oppHeads, obs, others);
                        }
                        // Fallback : bestOpen sans contrainte de sécurité (accepte espaces étroits)
                        if (dir<0) dir = bestOpen(snake, obs, others, /*ignoreSafety=*/true);
                    }

                    if (role == BLOCKER) {
                        // Intercepter la tête d'un adversaire plus court
                        bitset<2560> oppHeads;
                        for (int oid : g_oppIds) {
                            if (!all.count(oid)) continue;
                            const auto& opp = all.at(oid);
                            // N'intercepte que si on est plus long
                            if (snake.length() > opp.length()+1)
                                oppHeads.set(opp.head());
                        }
                        if (oppHeads.any())
                            dir = bfsToTargets(snake, oppHeads, obs, others);
                        // Si interception impossible, se rabat sur collect
                        if (dir<0) role = COLLECTOR;
                    }

                    if (role == COLLECTOR) {
                        // 2a. BFS vers énergie réservée à CE serpent
                        bitset<2560> myRes;
                        int bestDist=INT_MAX, myTarget=-1;
                        int x0=ex(snake.head()), y0=ey(snake.head());
                        for (int e=0; e<2560; e++) {
                            if (!reserved[e]) continue;
                            int d=abs(ex(e)-x0)+abs(ey(e)-y0);
                            if (d<bestDist) { bestDist=d; myTarget=e; }
                        }
                        if (myTarget>=0) myRes.set(myTarget);

                        int t=-1;
                        dir = bfsToTargets(snake, myRes, obs, others, &t);
                        // 2b. BFS vers énergie non réservée
                        if (dir<0) {
                            bitset<2560> free = energy & ~reserved;
                            dir = bfsToTargets(snake, free, obs, others, &t);
                            if (dir>=0 && t>=0) reserved.set(t);
                        }
                    }
                }

                // ── 3. BFS vers toute énergie (filet de sécurité) ────────────
                if (dir<0) dir = bfsToTargets(snake, energy, obs, others);

                // ── 4. bestOpen ───────────────────────────────────────────────
                if (dir<0) dir = bestOpen(snake, obs, others);
            }

            if (dir<0) dir=0; // UP par défaut absolu
            actions.push_back(to_string(sid)+" "+DNAME[dir]);
        }

        // ── MARK énergies réservées (visible sur la carte) ────────────────────
        int mc=0;
        for (int c=0; c<2560 && mc<4; c++) {
            if (!reserved[c]) continue;
            marks.push_back("MARK "+to_string(ex(c))+" "+to_string(ey(c)));
            mc++;
        }

        cerr << "DEBUG turn t="
             << chrono::duration_cast<chrono::milliseconds>(
                    chrono::steady_clock::now()-t0).count() << "ms" << endl;

        if (actions.empty()) {
            cerr << "DEBUG WARNING: no actions" << endl;
            for (int fid : aliveM) actions.push_back(to_string(fid)+" WAIT");
            if (actions.empty()) actions.push_back("WAIT");
        }

        bool first=true;
        for (auto& m : marks) { if (!first) cout<<";"; cout<<m; first=false; }
        for (auto& a : actions) { if (!first) cout<<";"; cout<<a; first=false; }
        cout<<"\n"<<flush;
    }
    return 0;
}