Submission #69276280

---

Source Code Expand

#pragma region MACRO
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vl = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i, n) for (auto &i : n)

template <class T1, class T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T1, class T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

struct init {
    init() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} init_;

template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &a) { return out << a.first << ' ' << a.second; }
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T, size_t N>
ostream &operator<<(ostream &out, const array<T, N> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T>
ostream &operator<<(ostream &out, const set<T> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T, typename U>
ostream &operator<<(ostream &out, const map<T, U> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << '\n';
    }
    return out;
}

#ifdef DEBUG
template <class T, class N>
void verr(const vector<T> &a, const N &n) {
    rep(i, n) cerr << a[i] << " ";
    cerr << endl;
}
template <class T, class N, size_t AN>
void verr(const array<T, AN> &a, const N &n) {
    rep(i, n) cerr << a[i] << " ";
    cerr << endl;
}
ll dbgt = 1;
void err() { cerr << "passed " << dbgt++ << endl; }
template <class H, class... T>
void err(H &&h, T &&...t) {
    cerr << h << (sizeof...(t) ? " " : "\n") << flush;
    if (sizeof...(t) > 0) err(forward<T>(t)...);
}
#else
void err() {}
template <class H, class... T>
void err(H &&h, T &&...t) {}
template <class H, class... T>
void verr(H &&h, T &&...t) {}
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

inline uint32_t pcg32() {
    static uint64_t x = 0x0123456789012345u;
    unsigned count = (unsigned)(x >> 61);
    x *= 3;
    x ^= x >> 22;
    return (uint32_t)(x >> (22 + count));
}
#pragma endregion

// 時間を出力
chrono::system_clock::time_point startTime, endTime;

// 経過時間(ms) を取得
int get_diff_time() {
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - startTime).count();
}

// [0, a)の整数乱数
inline int get_randint(int a) {
    return (long long)pcg32() * a >> 32;
}

// [0, 1]の乱数
inline double get_randdouble() {
    return pcg32() / (double)numeric_limits<uint32_t>::max();
}

constexpr int LOG_NUM = 50000;
array<double, LOG_NUM> init_log_table() {
    array<double, LOG_NUM> table;
    rep(i, LOG_NUM) table[i] = -log(get_randdouble());
    return table;
}
const array<double, LOG_NUM> log_table = init_log_table();

// パラメータ
constexpr int TIME_LIMIT = 1950;
constexpr double START_TEMP = 100, END_TEMP = 1;
constexpr int N = 500, M = 50;
constexpr ll e15 = 1000000000000000LL;
constexpr ll e12 = 1000000000000LL;
constexpr ll L = e15 - 2 * e12, R = e15 + 2 * e12;

double get_time_progress() {
    return get_diff_time() / (double)TIME_LIMIT;
}


struct Input {
    Input() {}
    void read() {
        int n;
        cin >> n;
        
    }
};

using Score = int;

struct State {
    static Input ip;

    Score score;
    State() {
    }

    bool isBetterThan(const State &other) const {
        return score < other.score;
    }

    // 操作列を出力
    void output() const {
    }
};

Input State::ip;

struct ActionMove {
    static bool Run(State &s, const double& threshold, const double& temp) {
        const Score preScore = s.score;
        const int diff = 0;

        if(diff > threshold) {
            // 不採用
            return false;
        }

        // 操作列を変更

        return true;
    }
};


State simulated_annealing(State s) {
    State bestState = s;
    err("start sa");
    err("start score", s.score);

    double temp = START_TEMP;
    int sa_count = 0;
    int diff_time = get_diff_time();

    int accepted_count = 0;
    bool update_best = false;

    while (true) {
        constexpr int mesure_cycle = (1 << 16) - 1;
        if ((sa_count & mesure_cycle) == 0) {
            diff_time = get_diff_time();
            if (diff_time > TIME_LIMIT) break;
            if(diff_time > 1900) update_best = true;

            // 線形
            // temp = START_TEMP + (END_TEMP - START_TEMP) * get_time_progress();
            // 指数
            temp = START_TEMP * pow(END_TEMP / START_TEMP, get_time_progress());
        }

        // double threshold = log_table[get_randint(LOG_NUM)] * temp;
        double threshold = 0;

        const int randv = get_randint(10);
        bool res = false;
        if (randv < 1) {
            res |= ActionMove::Run(s, threshold, temp);
        } else if (randv < 10) {
        }
        accepted_count += res;

        if (update_best && s.isBetterThan(bestState)) {
            bestState = s;
        }
        sa_count++;
    }

    err("sa count", sa_count);
    err("state score", bestState.score);
    err("accepted count", accepted_count);

    return bestState;
}

void run_input() {
    // State::ip.read();
    ll n, m, l, u;
    cin >> n >> m >> l >> u;
}

void solve() {
    vl A;
    ll BN = 16, T = 29;

    vl btotal(BN);
    rep(b, BN) {
        rep(i, T) {
            if (A.size() == N - M) break;
            btotal[b]++;
            A.eb(1ll << (42 - b - 1));
        }
    }
    rep(i, M) A.eb(L);

    rep(i, N) {
        cout<< A[i] << " ";
    }
    cout << endl;

    // Bの入力
    vl B(M);
    rep(i, M) {
        cin >> B[i];
        B[i] -= L;
    }

    vl AF(N);
    rep(i, M) AF[N - M + i] = i + 1;

    vl bvals(M);
    vl brest = btotal;
    using Pair = pair<ll, ll>;
    priority_queue<Pair, vector<Pair>, less<Pair>> pq;
    rep(i, M) {
        pq.push({B[i], i});
    }

    rep(b, BN) {
        ll shift = 1ll << (42 - b - 1);
        priority_queue<Pair, vector<Pair>, less<Pair>> npq;

        while(!pq.empty()) {
            auto [bv, bi] = pq.top(); pq.pop();
            if(bv < shift ||brest[b] == 0) {
                npq.push({bv, bi});
                continue;
            }
            bvals[bi] += shift;
            AF[b * T + (btotal[b] - brest[b])] = bi + 1;
            brest[b]--;
            bv -= shift;
            if(bv >= shift && brest[b] > 0) {
                pq.push({bv, bi});
            } else {
                npq.push({bv, bi});
            }
        }
        swap(pq, npq);
        // ll cnt = 0;
        // rep(i, M) {
        //     if(brest[b] == 0) break;
        //     if (!(B[i] >> (42 - b - 1) & 1)) continue;

        //     bvals[i] += shift;
        //     AF[b * T + cnt] = i + 1;
        //     cnt++;
        //     brest[b]--;
        // }
    }

    // rep(i, M) {
    //     ll minE = INF, minBit = -1;
    //     ll bv = B[i];
    //     rep(bit, 1 << 9) {
    //         ll shift = bit << 42 - 9;
    //         ll e = abs(bv - shift);
    //         if(chmin(minE, e)) {
    //             minBit = bit;
    //         }
    //     }

    //     rep(bi, 9) {
    //         if((minBit >> 9 - bi - 1) & 1) {
    //             AF[bi * M + i] = i + 1;
    //         }
    //     }
    // }

    rep(i, N) cout<< AF[i] << " ";
    cout << endl;
}

void run() {
    run_input();
    solve();
}

int main() {
    startTime = chrono::system_clock::now();
#ifdef TUNE
    // params
#endif
    run();
}

Submission Info

Compile Error

Main.cpp:1: warning: ignoring ‘#pragma region MACRO’ [-Wunknown-pragmas]
    1 | #pragma region MACRO
      | 
Main.cpp:125: warning: ignoring ‘#pragma endregion ’ [-Wunknown-pragmas]
  125 | #pragma endregion
      | 
Main.cpp: In static member function ‘static bool ActionMove::Run(State&, const double&, const double&)’:
Main.cpp:197:21: warning: unused variable ‘preScore’ [-Wunused-variable]
  197 |         const Score preScore = s.score;
      |                     ^~~~~~~~
Main.cpp:196:70: warning: unused parameter ‘temp’ [-Wunused-parameter]
  196 |     static bool Run(State &s, const double& threshold, const double& temp) {
      |                                                        ~~~~~~~~~~~~~~^~~~
Main.cpp: In instantiation of ‘void err(H&&, T&& ...) [with H = const char (&)[9]; T = {}]’:
Main.cpp:214:8:   required from here
Main.cpp:106:14: warning: unused parameter ‘h’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |          ~~~~^
Main.cpp: In instantiation of ‘void err(H&&, T&& ...) [with H = const char (&)[12]; T = {int&}]’:
Main.cpp:215:8:   required from here
Main.cpp:106:14: warning: unused parameter ‘h’ [-Wunused-parameter]
Main.cpp:106:21: warning: unused parameter ‘t#0’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |                 ~~~~^~~~
Main.cpp: In instantiation of ‘void err(H&&, T&& ...) [with H = const char (&)[9]; T = {int&}]’:
Main.cpp:254:8:   required from here
Main.cpp:106:14: warning: unused parameter ‘h’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |          ~~~~^
Main.cpp:106:21: warning: unused parameter ‘t#0’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |                 ~~~~^~~~
Main.cpp: In instantiation of ‘void err(H&&, T&& ...) [with H = const char (&)[15]; T = {int&}]’:
Main.cpp:256:8:   required from here
Main.cpp:106:14: warning: unused parameter ‘h’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |          ~~~~^
Main.cpp:106:21: warning: unused parameter ‘t#0’ [-Wunused-parameter]
  106 | void err(H &&h, T &&...t) {}
      |                 ~~~~^~~~

Judge Result