結果

問題 No.5020 Averaging
ユーザー ぴぃいいいいぴぃいいいい
提出日時 2024-02-29 01:55:06
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 892 ms / 1,000 ms
コード長 8,930 bytes
コンパイル時間 4,552 ms
コンパイル使用メモリ 211,648 KB
実行使用メモリ 19,504 KB
スコア 79,542,937
最終ジャッジ日時 2024-02-29 01:55:59
合計ジャッジ時間 47,521 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 779 ms
18,464 KB
testcase_01 AC 892 ms
19,360 KB
testcase_02 AC 859 ms
19,108 KB
testcase_03 AC 855 ms
19,108 KB
testcase_04 AC 793 ms
18,592 KB
testcase_05 AC 805 ms
18,604 KB
testcase_06 AC 810 ms
18,992 KB
testcase_07 AC 823 ms
18,612 KB
testcase_08 AC 860 ms
18,980 KB
testcase_09 AC 832 ms
18,872 KB
testcase_10 AC 806 ms
18,600 KB
testcase_11 AC 738 ms
18,348 KB
testcase_12 AC 773 ms
18,844 KB
testcase_13 AC 719 ms
18,108 KB
testcase_14 AC 774 ms
18,724 KB
testcase_15 AC 768 ms
18,728 KB
testcase_16 AC 745 ms
18,840 KB
testcase_17 AC 722 ms
18,584 KB
testcase_18 AC 832 ms
19,384 KB
testcase_19 AC 813 ms
19,096 KB
testcase_20 AC 769 ms
18,596 KB
testcase_21 AC 808 ms
18,992 KB
testcase_22 AC 730 ms
18,600 KB
testcase_23 AC 763 ms
18,840 KB
testcase_24 AC 729 ms
18,592 KB
testcase_25 AC 774 ms
19,232 KB
testcase_26 AC 837 ms
19,372 KB
testcase_27 AC 769 ms
19,116 KB
testcase_28 AC 777 ms
18,600 KB
testcase_29 AC 728 ms
18,472 KB
testcase_30 AC 797 ms
19,236 KB
testcase_31 AC 755 ms
18,588 KB
testcase_32 AC 724 ms
18,472 KB
testcase_33 AC 855 ms
19,120 KB
testcase_34 AC 748 ms
18,720 KB
testcase_35 AC 752 ms
18,844 KB
testcase_36 AC 779 ms
18,860 KB
testcase_37 AC 747 ms
18,464 KB
testcase_38 AC 770 ms
18,604 KB
testcase_39 AC 736 ms
18,344 KB
testcase_40 AC 735 ms
18,632 KB
testcase_41 AC 751 ms
18,224 KB
testcase_42 AC 748 ms
18,720 KB
testcase_43 AC 831 ms
18,996 KB
testcase_44 AC 860 ms
18,996 KB
testcase_45 AC 807 ms
18,748 KB
testcase_46 AC 701 ms
18,848 KB
testcase_47 AC 793 ms
19,504 KB
testcase_48 AC 784 ms
19,240 KB
testcase_49 AC 762 ms
18,992 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <utility>
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>
#include <optional>
#include <unordered_set>
#include <cassert>
#include <chrono>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using vll = vector<ll>;

inline double get_time() {
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}
double start_time = get_time();

struct IndexSet {
    vector<int> que;
    vector<int> pos;

    IndexSet() {}

    IndexSet(int n) : pos(n), que(n) {
        iota(pos.begin(),pos.end(),0);
        iota(que.begin(),que.end(),0);
    }

    void add(int v) {
        pos[v] = que.size();
        que.push_back(v);
    }

    void remove(int v) {
        int p = pos[v];
        int b = que.back();
        que[p] = b;
        que.pop_back();
        pos[b] = p;
        pos[v] = -1;
    }

    bool contains(int v) const {
        return pos[v] != -1;
    }

    int size() const {
        return que.size();
    }
};

struct IO{
    int n;
    vll a,b;
    IO(){}
    void input(){
        cin >> n;
        a.resize(n);
        b.resize(n);
        for(int i=0;i<n;i++){
            cin >> a[i] >> b[i];
            a[i] -= 500000000000000000ll;
            b[i] -= 500000000000000000ll;
        }
    }
};

//操作を表す構造体
struct Operation{
    size_t i;
};
//操作を元に戻すための情報を表す構造体
struct RollbackOperation{
    size_t i;
    double mul;
};

struct State{
    IO *io;
    double a,b;
    IndexSet unused;
    int cnt;

    //初期状態の生成
    State(IO &_io) : io(&_io){
        a = 0, b = 0;
        unused = IndexSet(io->n);
        cnt = 1;
    };
    //スコア計算
    ull score(){
        return max(abs(a),abs(b));
    };
    //ハッシュ値計算
    ull hash(){
        ull h = ull(a)^ull(b);
        /* for(int i=0;i<io->n;i++){
            if(!unused.contains(i)){
                h^=i;
            }
        } */
        return h;
    };
    //状態を更新せずスコアとハッシュのみを計算
    pair<ull,ull> try_apply(Operation op, ull score, ull hash){
        double ave_a = a + pow(0.5,cnt) * (double)io->a[op.i];
        double ave_b = b + pow(0.5,cnt) * (double)io->b[op.i];
        hash = ull(ave_a) ^ ull(ave_b);
        score = max(abs(ave_a),abs(ave_b));
        if(score == 0){
            cerr << "a : " << a << endl;
            cerr << "b : " << b << endl;
            cerr << "ave_a : " << ave_a << endl;
            cerr << "ave_b : " << ave_b << endl;
            cerr << "abs(ave_a) : " << abs(ave_a) << endl;
            cerr << "abs(ave_b) : " << abs(ave_b) << endl;
            exit(1);
        }
        return {score,hash};
    };
    //状態を更新する
    //元の状態に戻すための情報を返す
    RollbackOperation apply(Operation op){
        a += pow(0.5,cnt) * io->a[op.i]; 
        b += pow(0.5,cnt) * io->b[op.i];
        RollbackOperation rop = {op.i, pow(0.5,cnt)};
        cnt++;
        unused.remove(op.i);

        
        return rop;
    }
    //applyから返された情報を元に状態を戻す
    void rollback(RollbackOperation op){
        a -= op.mul * io->a[op.i];
        b -= op.mul * io->b[op.i];
        cnt--;
        unused.add(op.i);
    }
};

struct Node;

struct Cand{
    Operation op;
    shared_ptr<Node> parent;
    ull score;
    ull hash;
    ull p; //優先度
};

using Parent = optional<pair<Operation,shared_ptr<Node>>>;
using Children = vector<pair<Operation,weak_ptr<Node>>>;

struct Node{
    Parent parent;
    Children child;
    ull score;
    ull hash;

    Node(Parent parent, Children child, ull score, ull hash):
        parent(parent),child(child),score(score),hash(hash){}
};

// 多スタート用に構造体にまとめておくと楽
struct Tree{
    State state;
    shared_ptr<Node> node;
    ull rank;

    // 注意: depthは深くなっていくごとに-1されていく
    void dfs(vector<Cand>& next_states,bool one,ull& p,ull depth){
        if(depth==0){
            ull score=node->score;
            ull hash=node->hash;

            // 検算
            // assert(score==state.score());
            // assert(hash==state.hash());

            vector<Operation> ops; //次の操作を列挙
            for(int i=0;i<state.unused.que.size();i++){
                ops.emplace_back(state.unused.que[i]);
            }

            //次の操作を全部試す
            for(auto const& op:ops){
                auto [next_score,next_hash]=state.try_apply(op,score,hash);
                next_states.emplace_back(Cand{op,node,next_score,next_hash,p});
                p+=1;
            }
        }
        else{
            auto node_backup=node;
            auto child=&node_backup->child;
            // 有効な子だけにする
            child->erase(remove_if(child->begin(),child->end(),[](pair<Operation,weak_ptr<Node>>& x){return x.second.expired();}),child->end());

            bool next_one=one&child->size()==1;
            
            // 定数調整の必要あり
            if(depth==5){
                p=0;
            }
            ++rank;

            for(const auto& [op,ptr]:*child){
                node=ptr.lock();
                RollbackOperation backup=state.apply(op);
                dfs(next_states,next_one,p,depth-1);
                
                if(!next_one){
                    state.rollback(backup);
                }
            }
            
            if(!next_one){
                node=node_backup;
                --rank;
            }
        }
    }
};

vector<Operation> beam(IO &io){
    ull turn = io.n;
    constexpr ull beam_width = 5000;

    State state(io);
    ull score = state.score();
    ull hash = state.hash();

    // 検算
    assert(score==state.score());
    assert(hash==state.hash());

    Tree tree{move(state), shared_ptr<Node>(new Node(Parent(),Children(),score,hash)),0};

    vector<shared_ptr<Node>> cur{tree.node};
    vector<Cand> next_states;

    unordered_set<ull> hash_set;

    for(ull i=0;i<turn;i++){
        next_states.clear();
        ull tmp = 0;
        tree.dfs(next_states,true,tmp,i-tree.rank);

        #ifndef ONLINE_JUDGE
        cerr << "turn : " << i << " size : " << next_states.size() << endl;
        #endif

        if(i+1!=turn){
            //上位beam_width個だけ残す
            if(next_states.size() > beam_width){
                nth_element(next_states.begin(),next_states.begin()+beam_width,next_states.end(), [](Cand& a, Cand& b){
                    if(a.score == b.score){ return a.p > b.p; }
                    else return a.score < b.score;
                });
                next_states.erase(next_states.begin()+beam_width,next_states.end());
            }
            cerr << "best score : " << next_states[0].score << endl;
            
            cur.clear();
            hash_set.clear();
            for(const auto&[op,parent,next_score,next_hash,p]:next_states){
                //重複除去
                if(hash_set.count(next_hash)==0){
                    hash_set.insert(next_hash);
                    auto child_ptr=shared_ptr<Node>(new Node(Parent({op,parent}),Children(),score,hash));
                    parent->child.emplace_back(op,weak_ptr<Node>(child_ptr));
                    cur.emplace_back(child_ptr);
                }
            }
        }
    }

    //最良の状態を選択
    ull arg_min = -1;
    ull min = 1ull<<60;

    for(ull i=0;i<next_states.size();i++){
        if(next_states[i].score<=min){
            min=next_states[i].score;
            arg_min=i;
        }
    }
    auto [op,ptr,best_score,_,__]=next_states[arg_min];

    #ifndef ONLINE_JUDGE
    cerr << "best score : " << best_score << endl;
    cerr<<"rank: "<<turn-tree.rank<<endl;
    #endif

    vector<Operation> ret{op};

    // 操作の復元
    while(ptr->parent.has_value()){
        auto [op,parent]=ptr->parent.value();
        ret.emplace_back(op);
        ptr=parent;
    }

    reverse(ret.begin(),ret.end());
    return ret;
}

int main(){
    IO io;
    io.input();
    auto ops = beam(io);
    bool zero_merged = false;
    int last = -1;
    reverse(ops.begin(),ops.end());
    cout << ops.size()-1 << endl;
    for(auto op:ops){
        if(last == -1){
            last = op.i;
        }
        else{
            if(zero_merged){
                cout << 1 << " " << op.i+1 << endl;
            }
            else{
                cout << last+1 << " " << op.i+1 << endl;
            }
            last = op.i;
        }
        if(last == 0){
            zero_merged = true;
        }
    }

    #ifndef ONLINE_JUDGE
    cerr << "time : " << get_time()-start_time << "ms" << endl;
    #endif
}
0