sumoruさんの作品(ソースコード)

//------------------------------------------------------------------------------
/// @file
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2017 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください。
//------------------------------------------------------------------------------
 
#include "Answer.hpp"
 
using UFO = const hpc::UFO;
using House = const hpc::House;
using Stage = const hpc::Stage;
using Actions = hpc::Actions;
using TargetPositions = hpc::TargetPositions ;
using Vector2 = hpc::Vector2;
// using = hpc::;
 
void init(Stage& aStage);
void moveItems(Actions& aActions);
void moveUFOs(TargetPositions& aTargetPositions);
void finalize();
 
/// プロコン問題環境を表します。
namespace hpc {
 
//------------------------------------------------------------------------------
/// Answer クラスのコンストラクタです。
///
/// ここに最初のステージの開始前に行う処理を書くことができます。何も書かなくても構いません。
Answer::Answer()
{
}
 
//------------------------------------------------------------------------------
/// Answer クラスのデストラクタです。
///
/// ここに最後のステージの終了後に行う処理を書くことができます。何も書かなくても構いません。
Answer::~Answer()
{
}
 
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出されます。
///
/// ここで、各ステージに対して初期処理を行うことができます。
///
/// @param[in] aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
    ::init(aStage);
}
 
//------------------------------------------------------------------------------
/// 各ターンの、受け渡しフェーズの行動を指定してください。
///
/// - Actionクラスのstatic関数で行動を生成し、aActionsに格納してください。
/// - 行動は、配列のインデックスの昇順で実行されます。
/// - 同じUFOが複数回行動することもできます。
/// - UFOが箱を持っていないなど、必要な条件を満たしていない場合は何も起こりません。
///   条件の詳細はActionクラスを参照してください。
/// - 1回のフェーズの最大行動数は、Parameter::MaxActionPerTurnです。
/// - aActionsの要素の、UFOや家のインデックスが範囲外の場合、アサートに失敗します。
///
/// @param[in] aStage 現在のステージ。
/// @param[out] aActions この受け渡しフェーズの行動を指定する配列。
void Answer::moveItems(const Stage&, Actions& aActions)
{
    ::moveItems(aActions);
}
 
//------------------------------------------------------------------------------
/// 各ターンの、移動フェーズの行動を指定してください。
/// 
/// - 各UFOごとに、目標座標を指定してください。
/// - aTargetPositions[i]が、aStage.ufos()[i]の目標座標となります。
/// - aTargetPositions.count() == aStage.ufos().count()となるように、配列に座標を追加してください。
///   - 要素数が異なる場合はアサートに失敗します。
/// - aTargetPositionsの要素の値が NaN または ±Inf である場合、アサートに失敗します。
///
/// @param[in] aStage 現在のステージ。
/// @param[out] aTargetPositions 各UFOの目標座標を指定する配列。
void Answer::moveUFOs(const Stage&, TargetPositions& aTargetPositions)
{
    // g_Solver.moveUFOs(aStage, aTargetPositions);
    ::moveUFOs(aTargetPositions);
}
 
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出されます。
///
/// ここにステージ終了時の処理を書くことができます。何も書かなくても構いません。
///
/// @param[in] aStage 現在のステージ。
void Answer::finalize(const Stage&)
{
    ::finalize();
}
 
} // namespace
 
 
 
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
// enum : int { M = (int)1e9 + 7 };
// enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
// original header for printing various things
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
 
struct Target {
    int idx;
    float rad;
    Vector2 position;
    Target(){}
    Target(size_t i, House* h): idx(i), rad(h->radius()), position(h->pos()){}
    Target(size_t i, Vector2 p, float r): idx(i), rad(r), position(p){}
    operator int () const { return idx; }
    operator Vector2 () const { return position; }
    Vector2 pos() const { return position; }
    float radius() const { return rad; }
    float dist(const Vector2& p) const { return position.dist(p); }
    float squareDist(const Vector2& p) const { return position.squareDist(p); }
    // operator string () const { return to_string(pos().x) + ',' + to_string(pos().y); }
};
 
#ifdef LOCAL
#define Func(name)\
    template <class... A>\
    auto name(A... args){ return data.name(forward<A>(args)...); }
template <class T>
struct DebugDeque {
    deque<T> data;
    template <class... A>
    DebugDeque(A... args): data(forward<A>(args)...){ }
    Func(insert);
    Func(push_back);
    Func(push_front);
    Func(resize);
    Func(back);
    Func(pop_back);
    Func(pop_front);
    Func(size);
    Func(empty);
    Func(begin);
    Func(end);
    Func(rbegin);
    Func(rend);
    Func(clear);
    Func(emplace_back);
    T& operator [] (int idx){
        // return data[idx];
        return data.at(idx);
    }
};
// using deqTarg = DebugDeque<Target>;
// #define vector DebugDeque
#endif
 
using deqTarg = deque<Target>;
 
struct Worker {
    size_t idx;
    UFO* ufo;
    deqTarg targets;
    Worker(size_t i, UFO* u): idx(i), ufo(u){ }
    operator Vector2 () const { return ufo->pos(); }
    Vector2 pos() const { return ufo->pos(); }
    float radius() const { return ufo->radius(); }
    float dist(const Vector2& p) const { return pos().dist(p); }
    float squareDist(const Vector2& p) const { return pos().squareDist(p); }
    int items() const { return ufo->itemCount(); }
    float speed() const { return ufo->maxSpeed(); }
};
 
const int SEEK_ITEM = -2;
int turn, exTurn, exTurn2, game;
bool over;
mt19937 mt;
Vector2 center(375, 375);
Target centerT(SEEK_ITEM, center, 20);
vector<Worker> lworkers, sworkers; // large, small
using usTargets = unordered_set<Target, hash<int>>;
usTargets targets, waitings, delivered, allTargets;
vector<vector<Vector2>> posL;
 
void firstTargets();
void shortPath(Worker& w, deqTarg& v, Vector2 from, int beg, int end);
deqTarg nearTargets(usTargets& ts, Vector2 from, int size, int dist);
// void removeDupeTarget();
float moveTo(Vector2& from, const Vector2 to, const int len);
int moveTo2(Vector2& pos, const Worker& w, const Target to);
template <class T>
int calcTime(T& w, float len);
Vector2 go(Worker& w, int rate);
Vector2 go(Worker& w, Vector2 dest, int rate);
Vector2 go(Worker& w, Vector2 pos, int idx, Vector2 dest, int rate, int division = 500);
Vector2 go2(Worker& w, Vector2 pos, Target dest, Target dest2, int rate, int division);
Vector2 overBeh(Worker& w);
 
struct Crowd {
    Vector2 pos;
    usTargets hs;
    Crowd(){}
    Crowd(int x, int y, usTargets h): pos(x, y), hs(h){}
    operator Vector2 () const { return pos; }
    int num(){ return hs.size(); }
};
vector<Crowd> crowd;
 
void init(Stage& stage){
    turn = 0;
    exTurn = 0;
    exTurn2 = 0;
    over = false;
    lworkers.clear();
    sworkers.clear();
    targets.clear();
    delivered.clear();
    for(size_t i = 0; i < (size_t)stage.ufos().count(); i++){
        auto& u = stage.ufos()[i];
        (u.maxSpeed() == 5 ? lworkers : sworkers).emplace_back(i, &u);
    }
    for(size_t i = 0; i < (size_t)stage.houses().count(); i++){
        targets.emplace(i, &stage.houses()[i]);
        waitings.emplace(i, &stage.houses()[i]);
    }
    allTargets = targets;
    firstTargets();
}
 
void finalize(){
    printde(game, turn, '/', exTurn, exTurn2, delivered.size());
    game++;
}
 
void moveItems(Actions& actions){
    turn++;
    for(int i = 0; i < 2; i++){ for(auto& w : i ? sworkers : lworkers){
        if(hpc::Util::IsIntersect(w, centerT)){
            actions.add(hpc::Action::PickUp(w.idx));
            if(w.targets.size() && w.targets[0].idx == SEEK_ITEM){
                w.targets.pop_front();
            }
        }else if(i && w.targets.size() && w.targets[0].idx == SEEK_ITEM){
            for(auto& lw : lworkers){
                if(hpc::Util::IsIntersect(w, lw)){
                    actions.add(hpc::Action::Pass(lw.idx, w.idx));
                    w.targets.pop_front();
                    break;
                }
            }
        }
        int items = w.items();
        while(w.targets.size() && (w.targets[0].idx < 0 || items) && hpc::Util::IsIntersect(w, w.targets[0])){
            if(w.targets[0].idx >= 0){
                actions.add(hpc::Action::Deliver(w.idx, w.targets[0].idx));
                targets.erase(w.targets[0]);
                waitings.erase(w.targets[0]);
                delivered.insert(w.targets[0]);
                items--;
            }
            if(w.targets[0].idx != SEEK_ITEM){
                w.targets.pop_front();
            }else{
                break;
            }
        }
    } }
}
 
void moveUFOs(TargetPositions& targetPositions){
    for(int _ = 0; _ < 10; _++){ targetPositions.add(center); }
    for(auto& w : sworkers){ targetPositions[w.idx] = w; }
    for(int i = 0; i < 2; i++){ targetPositions[lworkers[i].idx] = crowd[i]; }
    if(!over && turn > 180){
        over = true;
        for(int i = 0; i < 2; i++){ for(auto& w : i ? lworkers : sworkers){
            w.targets.clear();
        } }
        targets = allTargets;
        for(auto e : delivered){
            targets.erase(e);
        }
    }
    for(int i = 0; i < 2; i++){ for(auto& w : i == 0 ? lworkers : sworkers){
        // removeDupeTarget();
        if(over){ 
            targetPositions[w.idx] = overBeh(w);
            continue;
        }
        while(w.targets.size() && delivered.count(w.targets[0])){
            w.targets.pop_front();
        }
        if(w.targets.size()){
            targetPositions[w.idx] = go(w, 98);
        }
        for(auto& lw : lworkers){
            if(w.targets.size() && w.targets[0].idx == SEEK_ITEM &&
               w.targets[0].squareDist(center) > 10 && w.squareDist(lw) < 900){
                if(targetPositions[lw.idx].squareDist(lw) <= 25){
                    targetPositions[w.idx] = go(w, targetPositions[lw.idx], 98);
                }else{
                    targetPositions[w.idx] = go(w, lw.pos() + (targetPositions[lw.idx] - lw).unit(5), 98);
                }
            }
        }
    } }
}
 
Vector2 overBeh(Worker& w){
    if(w.targets.empty() && w.items()){
        auto v = nearTargets(targets.size() ? targets : waitings, w, w.items(), 70);
        shortPath(w, v, w, 0, v.size());
        for(auto e : v){
            w.targets.push_back(e);
            targets.erase(e);
        }
        if(w.targets.size()){
            return go(w, 0);
        }
    }else if(w.targets.size() && w.items()){
        return go(w, 0);
    }else if(w.items() == 0){
        return center;
    }
    return w;
}
 
template <class T>
bool intersect(const Worker& w, const Vector2 pos, const T& w2){
    return pos.squareDist(w2) <= (w.radius() + w2.radius()) * (w.radius() + w2.radius());
}
 
template <class S, class T>
int tLen(const S& t1, const T& t2){
    return calcTime(t1, t1.dist(t2) - t1.radius() - t2.radius());
}
template <class S, class T>
int tLen(const S& w, const Vector2 t1, const T& t2){
    return calcTime(w, t1.dist(t2) - w.radius() - t2.radius());
}
template <class S, class T>
int tLen(const S& w, const Vector2 t1, const T& w2, const Vector2 t2){
    return calcTime(w, t1.dist(t2) - w.radius() - w2.radius());
}
 
template <class S>
int calcTime(S& w, float len){
    return (max(.0f, len) + w.speed() - 0.0001) / w.speed();
}
 
float moveTo(Vector2& from, const Vector2 to, const int len){
    if(len == 0){ return 0; }
    // float ret = from.dist(to);
    int ret = from.dist(to);
    if(ret <= len){
        from = to;
    }else{
        from += (to - from).unit(len);
        ret = len;
    }
    return ret;
}
 
int moveTo2(Vector2& pos, const Worker& w, const Target to){
    int speed = w.speed();
    int dist = max(0, int(pos.dist(to) - w.radius() - to.rad)) / speed * speed;
    int ret = (moveTo(pos, to, dist) + speed - 1) / speed;
    while(!intersect(w, pos, to)){
        ret++;
        moveTo(pos, to, speed);
    }
    return ret;
}
 
Vector2 go(Worker& w, int rate){
    return go(w, w, 0, w.targets[0], rate);
}
Vector2 go(Worker& w, Vector2 dest, int rate){
    return go(w, w, 0, dest, rate);
}
Vector2 go(Worker& w, Vector2 pos, int idx, Vector2 dest, int rate, int division){
    if(idx == (int)w.targets.size() - 1){
        return dest;
    }
    return go2(w, pos, Target(-1, dest, w.targets[idx].rad), w.targets[idx + 1], rate, division);
}
Vector2 go2(Worker& w, Vector2 pos, Target dest, Target dest2, int rate, int division){
    if(dest2.squareDist(dest) < 0.01){
        return dest;
    }
    // auto vec1 = dest.pos() - pos, vec2 = dest2.pos() - pos;
    // float angle12 = vec1.rotSign(vec2);
    // if(division == 500 && vec1.length() * abs(cos(angle12)) < dest.rad + w.radius() - 1){
    //     return dest2;
    // }
    auto dist = pos.dist(dest) - w.radius() - dest.rad;
    int frames = calcTime(w, dist);
    Vector2 rv = (dest2.pos() - dest).unit(dest.rad + w.radius());
    float angle = rv.rotSign(pos - dest);
    for(int i = 0; i <= division; i++){
        auto dest3 = dest.pos() + rv.rotateRad(angle * i / division) * rate / 100;
        if(dist <= w.speed()){
            if(pos.squareDist(dest3) <= w.speed() * w.speed()){
                return dest3;
                // return dest2.squareDist(dest3) <= dest2.squareDist(dest) ? dest3 : dest;
            }
        }else{
            if(calcTime(w, pos.dist(dest3)) <= frames){
                return dest3;
                // return dest2.squareDist(dest3) <= dest2.squareDist(dest) ? dest3 : dest;
            }
        }
    }
    return dest;
    // if(pos.dist(dest.pos() + rv * rate / 100) <= w.speed()){
    //     return dest.pos() + rv * rate / 100;
    // }
    // Vector2 ret = dest;
    // float mini = 1 << 30;
    // for(int i = 0; i <= division; i++){
    //     auto dest3 = pos + (dest.pos() - pos).rotateRad(M_PI / 4 * i / division - M_PI / 8);
    //     if(calcTime(w, pos.dist(dest3)) <= frames && dest3.dist(dest) < dest.rad + w.radius() - 2){
    //         auto dist2 = dest2.squareDist(dest3);
    //         if(dist2 < mini){
    //             mini = dist2;
    //             ret = dest3;
    //         }
    //     }
    // }
    // return ret;
}
 
// void removeDupeTarget(){
//     for(int i = 0; i < 2; i++){ for(auto& w1 : i ? lworkers : sworkers){
//         for(int j = 0; j < 2; j++){ for(auto& w2 : j ? lworkers : sworkers){
//             if(&w1 == &w2){ continue; }
//             if(w1.targets.empty() || w2.targets.empty()){ continue; }
//             if(w1.targets[0].idx != w2.targets[0].idx || w1.targets[0].idx < 0){ continue; }
//             if(tLen(w1, w1.targets[0]) < tLen(w2, w2.targets[0])){
//                 w2.targets.pop_front();
//             }else{
//                 w1.targets.pop_front();
//             }
//         } }
//     } }
// }
 
int setcrowd(int r, size_t outer, int wid){
    do{
        crowd = vector<Crowd>(2);
        usTargets hs = allTargets, next;
        r += 10;
        for(int h = 0; h < 2; h++){
            // for(int ii = 0; ii < 2; ii++){ for(int i = 20; i < 300; i += wid){
            //     int y = 375 + i * (ii * 2 - 1);
            //     for(int jj = 0; jj < 2; jj++){ for(int j = 20; j < 300; j += wid){
            //         int x = 375 + j * (jj * 2 - 1);
            //         next.clear();
            //         for(auto& t : hs){
            //             if(t.dist(Vector2(x, y)) <= r){
            //                 next.insert(t);
            //             }
            //         }
            //         if((int)next.size() > crowd[h].num()){
            //             crowd[h] = Crowd(x, y, next);
            //         }
            //     } }
            // } }
            for(int i = 100; i <= 650; i += wid){
                for(int j = 100; j <= 650; j += wid){
                    next.clear();
                    for(auto& t : hs){
                        if(t.squareDist(Vector2(j, i)) <= r * r){
                            next.insert(t);
                        }
                    }
                    if((int)next.size() > crowd[h].num()){
                        crowd[h] = Crowd(j, i, next);
                    }
                }
            }
            for(auto ho : crowd[h].hs){ hs.erase(ho); }
        }
    }while(allTargets.size() - crowd[0].num() - crowd[1].num() > outer);
    return r;
}
 
Target nearTarget(usTargets& ts, Vector2 from){
    Target ret;
    int mini = 1 << 30;
    for(auto e : ts){
        int dist = from.dist(e);
        if(dist < mini){
            mini = dist;
            ret = e;
        }
    }
    return ret;
}
Target farTarget(usTargets& ts, Vector2 from){
    Target ret;
    int maxi = -1;
    for(auto e : ts){
        int dist = from.dist(e);
        if(maxi < dist){
            maxi = dist;
            ret = e;
        }
    }
    return ret;
}
 
deqTarg nearTargets(usTargets& ts, Vector2 from, int size, int dist){
    if(ts.empty()){ return {}; }
    Target target = nearTarget(ts, from);
    vector<pair<int, Target>> v;
    for(auto e : ts){
        int d = e.squareDist(target);
        if(d < dist * dist){
            v.emplace_back(d, e);
        }
    }
    sort(v.begin(), v.end());
    deqTarg ret;
    for(int i = 0; i < min((int)v.size(), size); i++){
        ret.push_back(v[i].second);
    }
    return ret;
}
 
deqTarg greedyTargets(usTargets& ts, Vector2 from, int size, bool skip){
    if(ts.empty()){ return {}; }
    auto ts2 = ts;
    deqTarg ret;
    for(int i = 0; i < size && ts2.size(); i++){
        Target target = nearTarget(ts2, from);
        if(skip && mt() % 7 == 0 && ts2.size() >= 2){
            ts2.erase(target);
            Target target2 = nearTarget(ts2, from);
            ret.push_back(target2);
            from = target2;
            // moveTo2(from, sworkers[0], target2);
            ts2.erase(target2);
            ts2.insert(target);
        }else{
            ret.push_back(target);
            from = target;
            // moveTo2(from, sworkers[0], target);
            ts2.erase(target);
        }
    }
    return ret;
}
 
void shortPathR(Worker& w, deqTarg& v, Vector2 from, int beg, int end, int limit){
    int size = min({(int)v.size() - beg, 5, end - beg});
    if(size < 2){ return; }
    auto vv = v;
    vector<int> idxs(size), idxs1;
    iota(idxs.begin(), idxs.end(), beg);
    int mini = 1 << 30;
    do{
        int frame = 0;
        Vector2 pos = from.x == -1 ? v[idxs[0]] : from;
        for(auto i : idxs){ frame += moveTo2(pos, w, v[i]); }
        if(limit >= 0){
            int depFrame1 = max(0, limit - frame);
            int depFrame2 = max(0, limit - frame);
            // depFrame1 = tLen(w, pos, lworkers[0], posL[0][depFrame1]);
            // depFrame2 = tLen(w, pos, lworkers[1], posL[1][depFrame2]);
            frame += min({
                tLen(w, v[idxs.back()], centerT),
                tLen(w, v[idxs.back()], lworkers[0], posL[0][depFrame1]),
                tLen(w, v[idxs.back()], lworkers[1], posL[1][depFrame2]), });
                // tLen(w, pos, centerT), tLen(w, pos, lworkers[0], posL[0][depFrame1]), tLen(w, pos, lworkers[1], posL[1][depFrame2]),
        }
        if(frame < mini){
            mini = frame;
            idxs1 = idxs;
        }
    }while(next_permutation(idxs.begin(), idxs.end()));
    for(int i = 0; i < size; i++){
        v[beg + i] = vv[idxs1[i]];
    }
}
void shortPathR(Worker& w, deqTarg& v, int beg, int end, int limit){
    shortPathR(w, v, Vector2(-1, -1), beg, end, limit);
}
void shortPath(Worker& w, deqTarg& v, Vector2 from, int beg, int end){
    shortPathR(w, v, from, beg, end, -1);
}
 
bool setLWorkers(int limit){
    auto lw1 = lworkers;
    auto tg1 = targets;
    auto posL1 = posL;
    int mini =  1 << 30;
    for(int h = 0; h < 10; h++){
        auto lw = lworkers;
        auto tg = targets;
        auto posL0 = posL;
        for(int i = 0; i < 2; i++){
            auto &w = lworkers[i];
            auto pos = center;
            auto hs = crowd[i].hs;
            while(hs.size() && w.targets.size() < 40){
                auto target = nearTarget(hs, pos);
                if(h && mt() % 12 == 0){
                    hs.erase(target);
                    auto target2 = nearTarget(hs, pos);
                    hs.insert(target);
                    target = target2;
                }
                w.targets.push_back(target);
                hs.erase(target);
                moveTo2(pos, w, target);
            }
        }
 
        for(int i = 0; i < 2; i++){
            auto& w = lworkers[i];
            Vector2 pos = center;
            size_t wtidx;
            for(wtidx = 0; wtidx < w.targets.size(); wtidx++){
                auto p = pos;
                vector<Vector2> next;
                auto target = go(w, pos, wtidx, w.targets[wtidx], 98, 100);
                // int frames = tLen(w, pos, w.targets[wtidx]);
                // if((int)(posL[i].size() + frames) > limit){ break; }
                // for(int j = 0; j < frames; j++){
                //     next.push_back(p);
                //     moveTo(p, target, w.speed());
                // }
                while(!intersect(w, p, w.targets[wtidx])){
                    next.push_back(p);
                    moveTo(p, target, w.speed());
                }
                if((int)(posL[i].size() + next.size()) > limit){ break; }
                pos = p;
                posL[i].insert(posL[i].end(), next.begin(), next.end());
                targets.erase(w.targets[wtidx]);
            }
            w.targets.resize(wtidx);
 
            // if((int)w.targets.size() > 1){
            //     auto targets2 = w.targets;
            //     auto calc = [&](){
            //         int ret = 0;
            //         Vector2 pos2 = center;
            //         swap(targets2, w.targets);
            //         for(size_t idx2 = 0; idx2 < w.targets.size(); idx2++){
            //             ret += tLen(w, pos2, w.targets[idx2]);
            //             pos2 = go(w, pos2, idx2, w.targets[idx2], 98, 100);
            //         }
            //         swap(targets2, w.targets);
            //         return ret;
            //     };
            //     int mini = calc();
            //     for(int _ = 0; _ < 10; _++){
            //         auto b = targets2.back();
            //         targets2.pop_back();
            //         targets2.insert(targets2.begin() + mt() % targets2.size(), b);
            //         int frames = calc();
            //         if(frames < mini){
            //             mini = frames;
            //             w.targets = targets2;
            //         }else{
            //             targets2 = w.targets;
            //         }
            //     }
            // }
            // pos = center;
            // posL[i].clear();
            // for(wtidx = 0; wtidx < w.targets.size(); wtidx++){
            //     auto p = pos;
            //     vector<Vector2> next;
            //     auto target = go(w, p, wtidx, w.targets[wtidx], 98, 100);
            //     while(!intersect(w, p, w.targets[wtidx])){
            //         next.push_back(p);
            //         moveTo(p, target, w.speed());
            //     }
            //     if((int)(posL[i].size() + next.size()) > limit){ break; }
            //     pos = p;
            //     posL[i].insert(posL[i].end(), next.begin(), next.end());
            // }
 
            while((int)posL[i].size() <= limit){
                posL[i].push_back(pos);
                moveTo(pos, crowd[i], 5);
            }
        }
        if((int)targets.size() < mini){
            mini = targets.size();
            tg1 = targets;
            lw1 = lworkers;
            posL1 = posL;
        }
        targets = tg;
        lworkers = lw;
        posL = posL0;
    }
    targets = tg1;
    lworkers = lw1;
    posL = posL1;
    return true;
}
 
bool setSWorkers(int limit){
    auto nearBaseR = [&](Vector2 pos, int t){
        float d = max(.0f, pos.dist(center) - 22);
        Target dest = centerT;
        int len = 0;
        while(t > 0 && len < d){
            len += 12;
            t--;
            for(int i = 0; i < 2; i++){
                if(posL[i][t].dist(pos) - 12 < len){
                    return pair<int, Target>(i, Target(SEEK_ITEM, posL[i][t], 10));
                }
            }
        }
        return pair<int, Target>(-1, dest);
    };
    vector<int> items(10);
    auto checkBase = [&items](int idx, Target& n, int num){
        if(n.squareDist(center) > 1){
            if(idx >= 0 && items[idx] >= num){
                items[idx] -= num;
            }else{
                n = centerT;
            }
        }
    };
    items[0] = 40 - (int)lworkers[0].targets.size();
    items[1] = 40 - (int)lworkers[1].targets.size();
    auto tg = targets;
    auto sw = sworkers;
    auto it = items;
    int hend = 10;
    for(int h = 0; h < hend; h++){
        for(auto& w : sworkers){
            if(targets.empty()){ return true; }
            auto f = farTarget(targets, center);
            auto v = h == 0 ?
                nearTargets(targets, f, 5, 1000) :
                greedyTargets(targets, f, 5, true);
            shortPathR(w, v, 0, v.size(), limit);
            bool cont = true;
            int frame = 0;
            size_t idx;
            Vector2 pos = v[0];
            for(idx = 0; idx < v.size(); idx++){
                auto p2 = pos;
                int frame2;
                if(idx < v.size() - 1){
                    frame2 = frame + tLen(w, pos, v[idx]);
                    p2 = go2(w, pos, v[idx], v[idx + 1], 98, 100);
                    if(frame2 + tLen(w, p2, centerT) > limit){
                        p2 = go2(w, pos, v[idx], centerT, 98, 100);
                        if(frame2 + tLen(w, p2, centerT) > limit - 1){
                            cont = false;
                            break;
                        }
                    }
                }else{
                    frame2 = frame + moveTo2(p2, w, v[idx]);
                    if(frame2 + tLen(w, p2, centerT) > limit){
                        cont = false;
                        break;
                    }
                }
                pos = p2;
                frame = frame2;
            }
            if(idx == 0){ break; }
            v.resize(idx);
            for(auto e : v){ targets.erase(e); }
            pair<int, Target> base;
            int& bidx = base.first;
            Target& n = base.second;
            base = nearBaseR(pos, limit - frame);
            checkBase(bidx, n, v.size());
            frame += moveTo2(pos, w, n);
            v.push_back(n);
     
            while(cont && targets.size()){
                int t0 = frame, s0 = v.size();
 
                // auto v2 = greedyTargets(targets, pos, 5, false);
                // for(idx = 0; idx < v2.size(); idx++){
                //     auto p2 = pos;
                //     int frame2 = frame + moveTo2(p2, w, v2[idx]);
                //     if(frame2 + tLen(w, p2, centerT) > limit){ cont = false; break; }
                //     pos = p2;
                //     frame = frame2;
                //     v.push_back(v2[idx]);
                //     targets.erase(v2[idx]);
                // }
 
                for(idx = 0; idx < 5 && targets.size(); idx++){
                    n = nearTarget(targets, pos);
                    // bool skip = mt() % 20 == 0;
                    // if(skip && targets.size() >= 2){
                    //     targets.erase(n);
                    //     auto n2 = nearTarget(targets, pos);
                    //     targets.insert(n);
                    //     n = n2;
                    // }
                    auto p2 = pos;
                    int frame2 = frame + moveTo2(p2, w, n);
                    if(frame2 + tLen(w, p2, centerT) > limit){
                        cont = false;
                        for(auto n2 : targets){
                            p2 = pos;
                            frame2 = frame + moveTo2(p2, w, n2);
                            // frame2 = frame + tLen(w, pos, n2);
                            // p2 = go2(w, pos, n2, centerT, 98, 100);
                            if(frame2 + tLen(w, p2, centerT) < limit - 1){
                                pos = p2;
                                frame = frame2;
                                v.push_back(n2);
                                targets.erase(n2);
                                idx++;
                                break;
                            }
                        }
                        break;
                    }
                    pos = p2;
                    frame = frame2;
                    v.push_back(n);
                    targets.erase(n);
                }
 
                if(idx == 0){ break; }
                shortPathR(w, v, v[s0 - 1], s0, s0 + idx, limit - t0);
                base = nearBaseR(pos, limit - frame);
                if(cont){
                    checkBase(bidx, n, idx);
                }
                frame += moveTo2(pos, w, n);
                v.push_back(n);
            }
            while(v.size() && v.back().idx < 0){
                v.pop_back();
            }
     
            w.targets.insert(w.targets.end(), v.rbegin(), v.rend());
        }
        if(targets.empty()){
            return true;
        }
        targets = tg; sworkers = sw; items = it;
    }
    return false;
}
 
void firstTargets(){
    int n = targets.size();
    auto sw = sworkers, lw = lworkers, sw1 = sworkers, lw1 = lworkers;
    auto crowd1 = crowd;
    vector<vector<Vector2>> posL1, posL0(2, vector<Vector2> (1, center));
    vector<int> pivs;
    int mini = 130;
    unordered_set<int> checked;
    auto update = [&](int piv){
        if(checked.count(piv)){ return false; }
        checked.insert(piv);
        sworkers = sw; lworkers = lw;
        targets = allTargets;
        posL = posL0;
        if(setLWorkers(piv) && setSWorkers(piv)){
            pivs.push_back(piv);
            sw1 = sworkers; lw1 = lworkers;
            crowd1 = crowd;
            posL1 = posL;
            mini = piv;
            // for(int i = 0; i < 2; i++){ for(auto& w : i ? lworkers : sworkers){ printde(w.targets); } }
            return true;
        }
        return false;
    };
 
    pivs.clear();
    bool first = true;
    // for(int h = 4; h < 5; h++){ for(int g = 1; g < 2; g++){
    for(int h = 0; h < 6; h++){ for(int g = 1; g < 4; g++){ 
    // } }
        checked.clear();
        setcrowd(30, n * (0.415 + h * 0.06), 16 + g * 4);
        int l = 30;
        // int l = tLen(sworkers[0], center, farTarget(targets, center));
        while(first && l < mini){
            int piv = (l + mini) / 2;
            if(!update(piv)){ l = piv + 1; }
        }
        first = false;
        while(update(mini - 2) || update(mini - 1));
    } }
    printde(pivs);
 
    sworkers = sw1; lworkers = lw1;
    crowd = crowd1;
    posL = posL1;
 
    for(int i = 0; i < 2; i++){ for(auto& w : i ? lworkers : sworkers){
        while(w.targets.size() && w.targets[0].squareDist(center) < 10){
            w.targets.pop_front();
        }
    } }
 
    for(auto& w : sworkers){
        Vector2 pos = center;
        int t = 0;
        for(size_t i = 0; i < w.targets.size(); i++){
            if(w.targets[i].idx == SEEK_ITEM){
                int cnt = 0;
                bool cont = true;
                while(cont){
                    t++;
                    cnt++;
                if(cnt > 1000){ break; }
                    if(center.squareDist(w.targets[i]) < 3600 && tLen(w, pos, centerT) <= cnt){
                        w.targets[i] = centerT;
                        break;
                    }
                    for(int j = 0; j < 2; j++){
                        int tt = min(t, (int)posL[j].size() - 1);
                        if(posL[j][tt].squareDist(w.targets[i]) < 3600 && tLen(w, pos, lworkers[0], posL[j][tt]) <= cnt){
                            w.targets[i] = Target(SEEK_ITEM, posL[j][tt], 10);
                            cont = false; break;
                        }
                    }
                }
                moveTo(pos, w.targets[i], cnt * 12);
            }else{
                t += moveTo2(pos, w, w.targets[i]);
            }
            exTurn = max(exTurn, t + 1);
        }
    }
 
    targets = allTargets;
    for(int i = 0; i < 2; i++){ for(auto& w : i ? lworkers : sworkers){
        for(auto e : w.targets){
            targets.erase(e);
        }
    } }
    exTurn2 = pivs.size() ? pivs.back() : 0;
    // for(int i = 0; i < 2; i++){ for(auto& w : i ? lworkers : sworkers){ printde(w.targets); } }
}
 
// EOF