Submission #53164249

---

Source Code Expand

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

const double INF = 1e18;

class Xorshift {
    public:
        Xorshift(uint32_t seed): x_(seed) {
            // assert(seed);
        }

        uint32_t randrange(uint32_t stop) {
            // [0, stop)
            // assert(stop > 0);
            next();
            return x_ % stop;
        }

        uint32_t randrange(uint32_t start, uint32_t stop) {
            // [start, stop)
            // assert(start < stop);
            next();
            return start + x_ % (stop - start);
        }

        uint32_t randint(uint32_t a, uint32_t b) {
            // [a, b]
            // assert(a <= b);
            return randrange(a, b + 1);
        }

        double random() {
            // [0.0, 1.0]
            next();
            return static_cast<double>(x_) * (1.0 / static_cast<double>(UINT32_MAX));
        }

        double uniform(double a, double b) {
            // [a, b] or [b, a]
            return a + (b - a) * random();
        }

    private:
        void next() {
            x_ ^= x_ << 13;
            x_ ^= x_ >> 17;
            x_ ^= x_ << 5;
        }

        uint32_t x_;
};

class Timer {
    public:
        Timer() {
            begin();
            elapsed_time_ = 0.0;
        }

        void begin() {
            start_time_ = chrono::system_clock::now();
        }

        double get_time() {
            chrono::system_clock::time_point end_time = chrono::system_clock::now();
            elapsed_time_ = chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time_).count();
            elapsed_time_ *= 1e-9; // nanoseconds -> seconds
            return elapsed_time_;
        }

        double get_last_time() const {
            return elapsed_time_;
        }

        bool yet(double time_limit) {
            return get_time() < time_limit;
        }

        double progress(double time_limit) {
            return get_time() / time_limit;
        }

    private:
        chrono::system_clock::time_point start_time_;
        double elapsed_time_;
};

Xorshift rng(998244353);
Timer timer;
double time_limit = 1.9;
mt19937 engine(998244353);


int n,m;
double eps,delta;
const int MAX_T = 5000;
const double M = 100000.0;
const int B = 3000;
const double POINT_BUFFER = 2000.0;
bool dummy = false;


double clamp(double x){
    if (x <= -M){
        return -M+1;
    }
    if (x >= M){
        return M-1;
    }
    return x;
}

double normal(double x, double mean, double stdDev) {
    double v = (x - mean) / stdDev;
    return exp(-0.5 * v * v);
}

class P {
public:
    double x, y;

    // コンストラクタ
    P(double x = 0, double y = 0) : x(x), y(y) {}

    // 加算演算子のオーバーロード
    P operator+(const P& a) const {
        return P(x + a.x, y + a.y);
    }

    // 減算演算子のオーバーロード
    P operator-(const P& a) const {
        return P(x - a.x, y - a.y);
    }

    // スカラー乗算演算子のオーバーロード
    P operator*(double a) const {
        return P(x * a, y * a);
    }

    // 等価演算子
    bool operator==(const P& other) const {
        return (x == other.x) && (y == other.y);
    }

    // 不等価演算子
    bool operator!=(const P& other) const {
        return !(*this == other);
    }
    double dot(const P& a) const {
        return x * a.x + y * a.y;
    }

    double det(const P& a) const {
        return x * a.y - y * a.x;
    }

    double abs2() const {
        return dot(*this);
    }

    double abs() const {
        return sqrt(abs2());
    }

    static P gets(P cand, double lim){
        double now = cand.abs();
        P ret = cand * (lim / now);
        return ret;
    }

    // デバッグ用の出力演算子オーバーロード
    friend ostream& operator<<(ostream& os, const P& p) {
        return os << " " << p.x << " " << p.y << " ";
    }

    static double dist2_sp(const P& p1, const P& p2, const P& q) {
        if ((p2 - p1).dot(q - p1) <= 0.0) {
            return (q - p1).abs2();
        } else if ((p1 - p2).dot(q - p2) <= 0.0) {
            return (q - p2).abs2();
        } else {
            return dist2_lp(p1, p2, q);
        }
    }

    static double dist2_lp(const P& p1, const P& p2, const P& q) {
        double det = (p2 - p1).det(q - p1);
        return (det * det) / (p2 - p1).abs2();
    }

    static bool crs_sp(const P& p1, const P& p2, const P& q) {
        return (q - p1).dot(q - p2) <= 0.0;
    }

    static bool crs_lp(const P& p1, const P& p2, const P& q) {
        return (p2 - p1).det(q - p1) == 0.0;
    }

    static bool crs_ss(const P& p1, const P& p2, const P& q1, const P& q2) {
        auto sort = [](double a, double b) {
            return minmax(a, b);
        };

        auto [lp0, up0] = minmax(p1.x, p2.x);
        auto [lq0, uq0] = minmax(q1.x, q2.x);
        auto [lp1, up1] = minmax(p1.y, p2.y);
        auto [lq1, uq1] = minmax(q1.y, q2.y);

        if (up0 < lq0 || uq0 < lp0 || up1 < lq1 || uq1 < lp1) {
            return false;
        }
        return sig((p2 - p1).det(q1 - p1)) * sig((p2 - p1).det(q2 - p1)) <= 0
            && sig((q2 - q1).det(p1 - q1)) * sig((q2 - q1).det(p2 - q1)) <= 0;
    }

    static P proj(const P& p1, const P& p2, const P& q) {
        double d = (p2 - p1).abs2();
        if (d == 0.0) return p1;
        P r = p1 * d + (p2-p1) * (p2-p1).dot(q-p1);
        return P(r.x / d, r.y /d);
    }

    static P pi_ll(const P& p1, const P& p2, const P& q1, const P& q2) {
        double d = (q2 - q1).det(p2 - p1);
        if (d == 0.0) {
            return P(INF,INF);
        }
        P r = p1 * d + (p2 - p1) * (q2 - q1).det(q1 - p1);
        return P(r.x / d, r.y / d);
    }

    static int sig(double x) {
        if (x > 0) return 1;
        if (x < 0) return -1;
        return 0;
    }
};

vector<P> ps;
vector<bool> finished(10);

P now;
P v;
vector<pair<P,P>> walls;
vector<vector<double>> points_dists(100,vector<double>(100,INF));
vector<P> path_points;
int path_points_num = 0;
void Input() {
    cin >> n >> m >> eps >> delta;
    double x,y;
    cin >> x >> y;
    now = P(x,y);
    v = P(0,0);
    ps.resize(n);
    for (int i = 0; i < n; i++){
        double x,y;
        cin >> x >> y;
        ps[i] = P(x,y);
        
    }
    walls.resize(m+4);
    for (int i = 0; i < m; i++){
        double x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;

        walls[i] = {P(x1,y1),P(x2,y2)};
    }
    walls[m] = {P(-M,-M),P{M,-M}};
    walls[m+1] = {P(M,-M),P{M,M}};
    walls[m+2] = {P(M,M),P{-M,M}};
    walls[m+3] = {P(-M,M),P{-M,-M}};

    m += 4;

    for (int i = 0; i < n; i++){
        path_points.push_back(ps[i]);
    }

    for (int i = 0; i < m; i++){
        auto [p1,p2] = walls[i];
        
        P dif = p2 - p1;
        P buf = P::gets(dif,POINT_BUFFER);
        path_points.push_back(p2 + dif);
        path_points.push_back(p1 - dif);
    }

    path_points_num = path_points.size();

    for (int i = 0 ; i < path_points_num; i++){
        for (int j = 0; j < i; j++){
            bool ok = false;
            for (int x = 0; x < m; x++){
                if (P::crs_ss(path_points[i],path_points[j],walls[x].first,walls[x].second)) ok = true;
            }
            if (ok) continue;
            double d = (path_points[i]-path_points[j]).abs();
            points_dists[i][j] = d;
            points_dists[j][i] = d;
        }
    }

    


};


struct Solver{
    int best_score = 0;
    int current_score = 0;

    int turn = 0;
    P target_move;
    P target_path;
    bool need_update_path = true;


    // 終了判定
    void is_finish(){
        bool ok = true;
        for (int i = 0; i < n; i++){
            if (finished[i] == false) ok = false;
        }
        if (ok){
            exit(0);
        }
    }

    // p1 から p2 の線分が壁に当たるか 当たるなら true
    bool hit_wall(P p1, P p2){
        bool ok = false;
        for (int i = 0; i < m; i++){
            if (P::crs_ss(p1,p2,walls[i].first,walls[i].second)) ok = true;
        }
        return ok;
    }

    // p1 から dir 方向で最も近い壁との距離 必ず見つかる
    double nearest_wall(P p1, P dir){
        double dist = INF;
        P p2 = p1 + dir;
        for (int i = 0; i < m; i++){
            P cand = P::pi_ll(p1,p2,walls[i].first,walls[i].second);
            if (abs(cand.x - INF) < 1e-8) continue;;
            if ( P::sig(dir.det(walls[i].first-p1)) * P::sig(dir.det(walls[i].second-p1)) <= 0 && (cand-p1).dot(dir) >= 0){
                double dcand = (cand-p1).abs();
                if (dist > dcand){
                    dist = dcand;
                }
            } 
        }
        return dist;
    }

    // 粒子の候補に対して dir 方向の計測を行った時に期待される 距離の分散/距離の平均, 大きいほど嬉しい 
    double get_dir_var_max(vector<pair<P,P>> &candidate, P dir){
        vector<double> ds;
        long double ds_sum = 0;
        for (auto &c: candidate){
            double d = nearest_wall(c.first,dir);

            if (abs(d - INF) < 1e-8){
                assert (false);
            }
            ds.push_back(d);
            ds_sum += d;
            
        }
        long double avg = ds_sum / ds.size();
        long double var = 0;
        for (auto d: ds){
            var += (d-avg) * (d-avg);
        }
        var /= ds.size();

        return sqrt(var)/avg;
    }

    // p1 から p2 の線分で ポイントを通過するか 通過するなら true
    bool hit(P p1, P p2, int i){
        return P::dist2_sp(p1,p2,ps[i]) <= 1e6;
    }


    vector<pair<P,P>> accel_query(P a, vector<pair<P,P>>& candidate){

        cout << "A " << (int)a.x << " " << (int)a.y << endl;

        for (auto &c: candidate){
            c.second = c.second + a;
        }
        return candidate;
    }

    vector<pair<P,P>> measurement_query(P a, vector<pair<P,P>>& candidate){

        cout << "S " << (int)a.x << " " << (int)a.y << endl;

        double res;
        cin >> res;

        vector<double> probs;
        for (auto &cand: candidate){
            double d = nearest_wall(cand.first,a);
            double alpha = res / max(1e-9,d);
            probs.push_back(max(normal(alpha,1.0,delta),1e-18));
        }

        discrete_distribution weighted(probs.begin(),probs.end());

        vector<pair<P,P>> ncandidate;

        for (int _ = 0; _ < B; _++){
            ncandidate.push_back(candidate[weighted(engine)]);
        }
        swap(candidate,ncandidate);
        return candidate;
    }

    double update_current_state(vector<pair<P,P>>& candidate){
        now = P();
        v = P();
        for (auto [np,nv] : candidate){
            now = now + np;
            v = v + nv;
        }
        now = now * (1.0 / B);
        v = v * (1.0 / B);

        double sigma = 0;
        for (auto [np,nv]: candidate){
            sigma += (np - now).abs2();
        }
        sigma /= B;
        sigma = sqrt(sigma);

        return sigma;
    }

    void update_next_target(){
        if (need_update_path == false) return ;

        int is_end = 0;
        int n2 = 1<<n;
        for (int i = 0; i < n; i++){
            if (finished[i]) is_end |= 1<<i;
        }
        pair<int,int> empty = {-1,-1};
        vector<vector<double>> dp(n,vector<double>(n2,INF));
        vector<vector<pair<int,int>>> par(n,vector<pair<int,int>>(n2,empty));

        for (int i = 0; i < n; i++){
            if (finished[i]) continue;
            if (hit_wall(now,ps[i])) continue;
            dp[i][is_end|1<<i] = (now-ps[i]).abs();
        }
        for (int bi = 0; bi < n2; bi++){
            for (int i = 0; i < n; i++){
                if (dp[i][bi] == INF) continue;
                for (int ni = 0; ni < n; ni++){
                    if (bi >> ni & 1) continue;
                    if (points_dists[i][ni] == INF) continue;
                    int nbi = bi | 1 << ni;
                    int ndist = dp[i][bi] + points_dists[i][ni];
                    if (ndist < dp[ni][nbi]){
                        par[ni][nbi] = {i,bi};
                        dp[ni][nbi] = ndist;
                    }
                }
            }
        }
        double mi = INF;
        pair<int,int> last;
        for (int i = 0; i < n; i++){
            if (dp[i][n2-1] == INF) continue;

            if (mi > dp[i][n2-1]){
                mi = dp[i][n2-1];
                last = {i,n2-1};
            }
        }

        while (true){
            auto p = par[last.first][last.second];
            if (p == empty){
                need_update_path = false;
                target_path = ps[last.first];
                break;
            } else{
                last = p;
            }
        }

    }

    P decide_next_target(){

        update_next_target();
        return target_path;

        // double dist_max = INF;
        // for (int i = 0; i < n; i++){
        //     if (finished[i]) continue;

        //     // 壁に当たるかの判定
        //     if (hit_wall(now,ps[i])) continue;

        //     double dist = (now - ps[i]).abs2();

        //     if (dist < dist_max){
        //         dist_max = dist;
        //         target_move = ps[i];
        //     }
        // }
        // cout << "# target_move = " << target_move;
        // cout << "# dist = " << dist_max << (now-target_move).abs2() << endl;;

        // if (dist_max != INF){
        //     dummy = false;
        //     return target_move;
        // }

        // if (!dummy){
        //     dummy = true;
        //     int x = rng.randint(-100000,100000);
        //     int y = rng.randint(-100000,100000);
        //     target_move = P(x,y);
        // }

        // if (dummy && (hit_wall(now,target_move) || (now - target_move).abs2() < 1e8)){
        //     double best = INF;
        //     // cout << "# pos here" << endl;
        //     for (int _ = 0; _ < 10; _++){
        //         int x = rng.randint(-95000,95000);
        //         int y = rng.randint(-95000,95000);
        //         P q = P(x,y);
        //         // cout << "# q cand = " << q << endl;
        //         if (hit_wall(now,q)) continue;
        //         for (int i = 0; i < n; i++){
        //             if (finished[i]) continue;
        //             double dist = (now - q).abs() + (q - ps[i]).abs();
        //             if (hit_wall(q,ps[i])){
        //                 dist = 1e10 * rng.uniform(1,2);
        //             }
        //             if (best > dist){
        //                 best = dist;
        //                 target_move = q;
        //             }
        //         }
        //     }
        //     // cout << "# best = " << best << " ntarget = " << target_move << endl;
        // }
    
        // return target_move;
    }

    vector<pair<P,P>> next_action(P target, double sigma, int turn, vector<pair<P,P>>& candidate){
        P dir = target - now;
        P a = dir * min((2000.0 / dir.abs()),1.0) - v;
        if (a.abs() > 498.0){
            a = a * (498.0 / a.abs());
        }
        // 条件を満たせば加速
        if (a != P() && (turn%2 == 0 || sigma < 1000.0)){
            return accel_query(a,candidate);
        }

        // 計測の方向を最適化

        vector<P> cand;
        for (int i = 0; i < m; i++){
            if (i < m-4){
                cand.push_back(walls[i].first-now);
                cand.push_back(walls[i].second-now);
            } else{
                cand.push_back(walls[i].first-now);
            }
            cand.push_back(P::proj(walls[i].first,walls[i].second,now) - now);
        }
        vector<P> ncand;
        swap(cand,ncand);

        for (auto v: ncand){
            double d = v.abs();
            if (d > 1e5){
                v = v * (99998.0 / d);
            }
            v = P((int)v.x,(int)v.y);
            if (v.abs2() > 0.0){
                cand.push_back(v);
            }
        }
        vector<P> targets(2);

        if (timer.get_time() >= 1.5){
            vector<double> scores(2,INF);

            for (auto dir: cand){
                double d = nearest_wall(now,dir);
                if (d < scores[1]){
                    scores[1] = d;
                    targets[1] = dir;
                } else{
                    continue;
                }
                if (scores[1] < scores[0]){
                    swap(scores[1],scores[0]);
                    swap(targets[1],targets[0]);
                }
            }
        } else {
            vector<double> scores(2,-1.0);
            for (auto dir : cand){
                double d = get_dir_var_max(candidate,dir);
                if (d > scores[1]){
                    scores[1] = d;
                    targets[1] = dir;
                } else{
                    continue;
                }
                if (scores[1] > scores[0]){
                    swap(scores[1],scores[0]);
                    swap(targets[1],targets[0]);
                }
            }
        }
        
        if (rng.randrange(0,4) < 3){
            return measurement_query(targets[0],candidate);
        } else{
            return measurement_query(targets[1],candidate);
        }
       
        

    }

    vector<pair<P,P>> update_result(vector<pair<P,P>>& candidate){
        
        mt19937 gen(998244353);
        normal_distribution<double> normal_dist(0.0,eps);

        int c,h;
        cin >> c >> h;
        cout << "# c = " << c << " h = " << h << endl;

        if (c){
            current_score -= 100;
        }
        if (h){
            current_score += h * 1000;
        }

        vector<bool> new_finished(n);
        if (h){
            need_update_path = true;
            for (int i = 0 ; i < h; i++){
                int x;
                cin >> x;
                new_finished[x] = true;
            }
        }

        vector<pair<P,P>> saved = candidate;
        int empty = 0;
        cout << "# start at " << candidate.size() << endl;
        for (int _ = 0; _ < 10; _++){
            // if (_) break;

            // cout << "# loop = " << _ << endl;
            for (auto &cand : candidate){
                double r1 = normal_dist(engine);
                double r2 = normal_dist(engine);
                // cout << "# " << cand.first << " " << cand.second << " " << r1 << " " << r2 << endl;
                cand.second.x += r1;
                cand.second.y += r2;
            }

            vector<pair<P,P>> ncandidate;
            for (auto &cand: candidate){
                if (hit_wall(cand.first,cand.first+cand.second) == c){
                    ncandidate.push_back(cand);
                }
            }
            if (ncandidate.size()){
                cout << "# delete after size = " << ncandidate.size() << endl;
                swap(candidate,ncandidate);
                while (candidate.size() < B){
                    candidate.push_back(candidate[rng.randrange(candidate.size())]);
                }
            } else{
                candidate = saved;
                empty++;
                cout << "# empty before " << endl;
                continue;  
            }

            if (c == 1){
                cout << "# hit " << endl;
                for (auto &cand: candidate){
                    cand.second = P(0,0);
                }
                for (int i = 0; i < n; i++){
                    if (new_finished[i]) finished[i] = true;
                }
                return candidate;

            } else{
                for (auto &cand: candidate){
                    cand.first = cand.first + cand.second;
                    cand.first.x = clamp(cand.first.x);
                    cand.first.y = clamp(cand.first.y);

                    
                }
                bool ok = true;

                for (int i = 0; i < n; i++){
                    if (finished[i]) continue;

                    ncandidate.clear();
                    for (auto &cand: candidate){
                        if (hit(cand.first-cand.second,cand.first,i) == new_finished[i]){
                            ncandidate.push_back(cand);
                        }
                    }
                    cout << "# delete after size2 = " << i << " " << ncandidate.size() << endl;

                    if (ncandidate.size()){
                        swap(candidate,ncandidate);
                        while (candidate.size() < B){
                            candidate.push_back(candidate[rng.randrange(candidate.size())]);
                        }
                    } else{
                        candidate = saved;
                        ok = false;
                        break;
                    }
                }
                if (!ok){
                    empty++;
                    continue;
                }
                for (int i = 0; i < n; i++){
                    if (new_finished[i]) finished[i] = true;
                }
                return candidate;

            }
            break;

        }
        
        for (int i = 0; i < n; i++){
            if (new_finished[i]) finished[i] = true;
        }
        if (c == 1){
            for (auto &cand: candidate){
                cand.first.x += 2e4 * rng.uniform(-1.0,1.0);
                cand.first.y += 2e4 * rng.uniform(-1.0,1.0);
                cand.first.x = clamp(cand.first.x);
                cand.first.y = clamp(cand.first.y);
                cand.second = P(0,0);
            }
        } else{
            for (auto &cand: candidate){
                cand.first = cand.first + cand.second;
                cand.first.x = clamp(cand.first.x);
                cand.first.y = clamp(cand.first.y);
            }

            for (int i = 0; i < n; i++){
                if (new_finished[i]){
                    for (auto &cand: candidate){
                        cand.first = ps[i] + cand.second;
                        cand.first.x = clamp(cand.first.x);
                        cand.first.y = clamp(cand.first.y);
                    }

                }
            }

            

        }

        cout << "# empty = " << empty << endl;

        return candidate;
    
    }
    void escape(int turn){
        for (int t = turn ; t < MAX_T; t++){
            cout << "A 0 0" << endl; 
        }
        exit(0);
    }

    void solve(){

        vector<pair<P,P>> candidate(B,{now,v});
        
        for (int t = 0; t < MAX_T; t++){
            best_score = max(best_score,current_score);
            current_score -= 2;
            cout << "#turn = " << t << " eps = " << eps << " delta = " << delta << endl;
            cout << "# ";
            for (auto f : finished){
                cout << (int)f << " ";
            }
            cout << endl;
            // 全て通過したら終了
            is_finish();

            if (!timer.yet(time_limit)){
                escape(t);
            }

            // 推定情報を更新
            double sigma = update_current_state(candidate);
            cout << "#p_pred = " << now << endl;
            cout << "#v_pred = " << v << endl;
            cout << "#sigma = " << sigma << endl;

  
            // 次の目標を決定
            P target = decide_next_target();

            // 行動を決定
            candidate = next_action(target,sigma,t,candidate);

            // 結果による更新
            candidate = update_result(candidate);
        }

        cout << "#end at " << timer.get_time() << endl;
        cout << "#score = " << best_score << endl;
        
    }
};
int main() {
    Input();
    Solver solver = Solver();
    solver.solve();

    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In static member function ‘static bool P::crs_ss(const P&, const P&, const P&, const P&)’:
Main.cpp:200:14: warning: variable ‘sort’ set but not used [-Wunused-but-set-variable]
  200 |         auto sort = [](double a, double b) {
      |              ^~~~
Main.cpp: In function ‘void Input()’:
Main.cpp:283:11: warning: variable ‘buf’ set but not used [-Wunused-but-set-variable]
  283 |         P buf = P::gets(dif,POINT_BUFFER);
      |           ^~~

Judge Result