Submission #67600472

---

Source Code Expand

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;

#define debug(var)  do{std::cout << #var << " : \n";view(var);}while(0)
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } }

// #define DEBUG

#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif

ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";


unsigned int randxor(){
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}

struct Timer {
    public:
        Timer(int limit){
            start = chrono::high_resolution_clock::now();
            goal = start + chrono::milliseconds(limit);
        }

        inline double rate(){
            return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
        }

        inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}

    private:
        chrono::high_resolution_clock::time_point start;
        chrono::high_resolution_clock::time_point goal;  
};

double log_table[70000];
//variable
constexpr int TIME_LIMIT = 2990;
constexpr int N = 30;
constexpr int geta = 40;
int b1, b2, b3;
int L[N * N], R[N * N];
bitset<N * N> cantmove;
vi ok, ok4;

namespace simulated_annealing {

constexpr int transition_num = 4;
int transition_count[transition_num];
int success_count[transition_num];

using Cost = int;

struct Config {
    int time_limit;
    int temperature_type;
    double start_temp, goal_temp;
    int probability[transition_num];
};

struct State {
    Cost score;
    array<int, N * N> A;
    array<int, N> sh, sw;
    array<int, 280> SCORE;
    bitset<320> cnt;

    State(){
        score = 0;
    }

    void operator=(const State &other) {
        score = other.score;
        A = other.A;
    }

    void init(){
        fill(all(SCORE), 0);
        SCORE[b1] = b1;
        SCORE[b2] = b2;
        SCORE[b3] = b3;
        rep(i, N * N) A[i] = randint(L[i], R[i]);
        score = CalcScore();
    }

    Cost SubCalcScoreH(int i){
        cnt.reset();
        int sm = geta;
        Cost ret = 0;
        cnt.set(sm);
        for (int j = 0; j < N; ++j){
            sm += A[i * N + j];
            cnt.set(sm);
            if (cnt[sm - b1]) ret += b1;
            if (cnt[sm - b2]) ret += b2;
            if (cnt[sm - b3]) ret += b3;
        }
        return ret;
    }
    
    Cost SubCalcScoreW(int j){
        cnt.reset();
        int sm = geta;
        Cost ret = 0;
        cnt.set(sm);
        for (int i = 0; i < N; ++i){
            sm += A[i * N + j];
            cnt.set(sm);
            if (cnt[sm - b1]) ret += b1;
            if (cnt[sm - b2]) ret += b2;
            if (cnt[sm - b3]) ret += b3;
        }
        return ret;
    }

    Cost CalcScore(Cost threshold = inf){
        Cost ret = 0;
        rep(i, N) sh[i] = SubCalcScoreH(i);
        rep(j, N) sw[j] = SubCalcScoreW(j);
        rep(i, N){
            ret += sh[i];
            ret += sw[i];
        }
        return ret;
    }

    void transition01(Cost &threshold){ // 1 point change
        transition_count[0]++;
        int t = ok[randint(0, len(ok))];
        int i = t / N, j = t % N;
        int c = randint(L[t], R[t]);
        int lastc = A[t];
        while (lastc == c){
            c = randint(L[t], R[t]);
        }

        Cost new_score = score - sh[i] - sw[j];
        A[t] = c;
        Cost nsh = SubCalcScoreH(i), nsw = SubCalcScoreW(j);
        new_score += nsh + nsw;

        if (new_score >= threshold){
            success_count[0]++;
            score = new_score;
            sh[i] = nsh;
            sw[j] = nsw;
        }else{
            A[t] = lastc;
        }
    }

    void transition02(Cost &threshold){ // adjacent change h
        transition_count[1]++;
        int i = randint(0, N), j = randint(0, N - 1);
        while (cantmove[i * N + j] || cantmove[i * N + j + 1]){
            i = randint(0, N);
            j = randint(0, N - 1);
        }
        int lastc1 = A[i * N + j], lastc2 = A[i * N + j + 1];
        int l = max(L[i * N + j] - lastc1, lastc2 - R[i * N + j + 1] + 1);
        int r = min(R[i * N + j] - lastc1, lastc2 - L[i * N + j + 1] + 1);
        if (r <= l || (l + 1 == r && l == 0)) return;
        int d = randint(l, r);
        while (d == 0) d = randint(l, r);
        int c1 = lastc1 + d, c2 = lastc2 - d;
        
        Cost new_score = score - sh[i] - sw[j] - sw[j + 1];
        
        A[i * N + j] = c1;
        A[i * N + j + 1] = c2;
        Cost nsh = SubCalcScoreH(i), nsw1 = SubCalcScoreW(j), nsw2 = SubCalcScoreW(j + 1);
        new_score += nsh + nsw1 + nsw2;
        if (new_score >= threshold){
            success_count[1]++;
            score = new_score;
            sh[i] = nsh;
            sw[j] = nsw1;
            sw[j + 1] = nsw2;
        }else{
            A[i * N + j] = lastc1;
            A[i * N + j + 1] = lastc2;
        }
    }

    void transition03(Cost &threshold){ // adjacent change w
        transition_count[2]++;
        int i = randint(0, N - 1), j = randint(0, N);
        while (cantmove[i * N + j] || cantmove[i * N + j + N]){
            i = randint(0, N - 1);
            j = randint(0, N);
        }
        int lastc1 = A[i * N + j], lastc2 = A[i * N + j + N];
        int l = max(L[i * N + j] - lastc1, lastc2 - R[i * N + j + N] + 1);
        int r = min(R[i * N + j] - lastc1, lastc2 - L[i * N + j + N] + 1);
        if (r <= l || (l + 1 == r && l == 0)) return;
        int d = randint(l, r);
        while (d == 0) d = randint(l, r);

        int c1 = lastc1 + d, c2 = lastc2 - d;
        
        Cost new_score = score - sh[i] - sh[i + 1] - sw[j];
        
        A[i * N + j] = c1;
        A[i * N + j + N] = c2;
        Cost nsh1 = SubCalcScoreH(i), nsh2 = SubCalcScoreH(i + 1), nsw = SubCalcScoreW(j);
        new_score += nsh1 + nsh2 + nsw;
        if (new_score >= threshold){
            success_count[2]++;
            score = new_score;
            sh[i] = nsh1;
            sh[i + 1] = nsh2;
            sw[j] = nsw;
        }else{
            A[i * N + j] = lastc1;
            A[i * N + j + N] = lastc2;
        }
    }

    void transition04(Cost &threshold){ // adjacent change h w
        transition_count[3]++;
        int t = ok4[randint(0, len(ok4))];
        int i11 = t, i12 = t + 1, i21 = t + N, i22 = t + N + 1;
        int lastc11 = A[i11], lastc12 = A[i12], lastc21 = A[i21], lastc22 = A[i22];
        int l = max({lastc12 - R[i12] + 1, lastc21 - R[i21] + 1, L[i11] - lastc11, L[i22] - lastc22});
        int r = min({lastc12 - L[i12] + 1, lastc21 - L[i21] + 1, R[i11] - lastc11, R[i22] - lastc22});
        if (r <= l || (l + 1 == r && l == 0)) return;
        int d = randint(l, r);
        while (d == 0) d = randint(l, r);
        int c11 = lastc11 + d, c12 = lastc12 - d, c21 = lastc21 - d, c22 = lastc22 + d;
        int i = t / N, j = t % N;
        Cost new_score = score - sh[i] - sh[i + 1] - sw[j] - sw[j + 1];
        
        Cost nsh1 = sh[i], nsh2 = sh[i + 1], nsw1 = sw[j], nsw2 = sw[j + 1];
        for (int nj = j - 1, sm1 = A[i11], sm2 = A[i21]; nj >= 0; --nj){
            sm1 += A[i * N + nj];
            sm2 += A[i * N + nj + N];
            nsh1 -= SCORE[sm1];
            nsh1 += SCORE[sm1 + d];
            nsh2 -= SCORE[sm2];
            nsh2 += SCORE[sm2 - d];
        }
        for (int nj = j + 2, sm1 = A[i12], sm2 = A[i22]; nj < N; ++nj){
            sm1 += A[i * N + nj];
            sm2 += A[i * N + nj + N];
            nsh1 -= SCORE[sm1];
            nsh1 += SCORE[sm1 - d];
            nsh2 -= SCORE[sm2];
            nsh2 += SCORE[sm2 + d];
        }
        for (int ni = i - 1, sm1 = A[i11], sm2 = A[i12]; ni >= 0; --ni){
            sm1 += A[ni * N + j];
            sm2 += A[ni * N + j + 1];
            nsw1 -= SCORE[sm1];
            nsw1 += SCORE[sm1 + d];
            nsw2 -= SCORE[sm2];
            nsw2 += SCORE[sm2 - d];
        }
        for (int ni = i + 2, sm1 = A[i21], sm2 = A[i22]; ni < N; ++ni){
            sm1 += A[ni * N + j];
            sm2 += A[ni * N + j + 1];
            nsw1 -= SCORE[sm1];
            nsw1 += SCORE[sm1 - d];
            nsw2 -= SCORE[sm2];
            nsw2 += SCORE[sm2 + d];
        }
        new_score += nsh1 + nsh2 + nsw1 + nsw2;
        if (new_score >= threshold){
            success_count[3]++;
            score = new_score;
            sh[i] = nsh1;
            sh[i + 1] = nsh2;
            sw[j] = nsw1;
            sw[j + 1] = nsw2;
            A[i11] = c11;
            A[i12] = c12;
            A[i21] = c21;
            A[i22] = c22;
        }
    }
};

State simulated_annealing(const Config& config, State state) {
    State best;
    Timer timer(config.time_limit);
    int roop = 0;
    double tmp = config.start_temp;
    double rate = 0;
    while (true){
        roop++;
        int randomint = randint(0, 100);
        Cost threshold = state.score + tmp * log_table[randint(0, 70000)];

        if (randomint < config.probability[0]){ // transition 01
            state.transition01(threshold);
        }else if (randomint < config.probability[1]){
            state.transition02(threshold);
        }else if (randomint < config.probability[2]){
            state.transition03(threshold);
        }else{
            state.transition04(threshold);
        }

        if (best.score < state.score){ // update best
            best = state;
        }

        if (roop % 10000 == 0){
            // if (roop % 1000000 == 0) cerr << state.score << " " << best.score << endl;
            rate = timer.rate();
            tmp = config.start_temp + rate * (config.goal_temp - config.start_temp);
            // if (config.temperature_type == 0){
            // }else{
            //     tmp = config.start_temp * pow(config.goal_temp / config.start_temp, rate);
            // }
            if (rate > 1.0){
                break;
            }
        }
    }
    cerr << "roop : " << roop << endl;
    cerr << "score : " << best.score << endl;
    rep(i, transition_num) cerr << "transition" << i << " conversion rate : " << fixed << setprecision(4) << success_count[i] / (double)transition_count[i] * 100 << " %  " << success_count[i] << " / " << transition_count[i] << endl;
    return best;
};

}// namespace simulated_annealing

struct Solver{
    simulated_annealing::State ans;
    void input(){
        if (DEBUGMODE){
            ifstream in(inputfile);
            cin.rdbuf(in.rdbuf());
            int a; cin >> a >> b1 >> b2 >> b3;
            rep(i, N) rep(j, N) cin >> L[i * N + j];
            rep(i, N) rep(j, N) cin >> R[i * N + j];
        }else{
            int a; cin >> a >> b1 >> b2 >> b3;
            rep(i, N) rep(j, N) cin >> L[i * N + j];
            rep(i, N) rep(j, N) cin >> R[i * N + j];
        }
    }

    void init(){
		double n = 1 / (double)(2 * 70000);
		for (int i = 0; i < 70000; i++) {
			log_table[i] = log(((double)i / 70000) + n);
		}
        cantmove.reset();
        rep(i, N * N){
            if (L[i] == R[i]) cantmove.set(i);
            else{
                ok.push_back(i);
                if (i % N < N - 1 && i + N + 1 < N * N && L[i + 1] < R[i + 1] && L[i + N] < R[i + N] && L[i + N + 1] < R[i + N + 1]) ok4.push_back(i);
            }
            R[i]++;
        }
    }

    void output(){
        if (DEBUGMODE){
            rep(i, N){
                rep(j, N) wrt << ans.A[i * N + j] << " ";
                wrt << endl;
            }
        }else{
            rep(i, N){
                rep(j, N) cout << ans.A[i * N + j] << " ";
                cout << endl;
            }
        }
    }

    void run(){
        Timer timer(TIME_LIMIT);
        input();
        init();
        simulated_annealing::Config config = {
            TIME_LIMIT - timer.get_time(),
            0,
            30.0,
            10.0,
            {20, 23, 26, 100}
        };
        simulated_annealing::State state;
        state.init();
        ans = simulated_annealing::simulated_annealing(config, state);
        output();
    }
};

int main(){
    wrt.open(outputfile, ios::out);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver solver;
    solver.run();
    wrt.close();
    return 0;
}

Submission Info

Compile Error

./Main.cpp:4:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC optimize("O3")
            ^
./Main.cpp:5:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC optimize("unroll-loops")
            ^
./Main.cpp:147:25: warning: unused parameter 'threshold' [-Wunused-parameter]
    Cost CalcScore(Cost threshold = inf){
                        ^
./Main.cpp:103:10: warning: definition of implicit copy constructor for 'State' is deprecated because it has a user-provided copy assignment operator [-Wdeprecated-copy-with-user-provided-copy]
    void operator=(const State &other) {
         ^
./Main.cpp:354:12: note: in implicit copy constructor for 'simulated_annealing::State' first required here
    return best;
           ^
./Main.cpp:19:10: warning: unused variable 'pi' [-Wunused-const-variable]
const ld pi = 3.141592653589793;
         ^
./Main.cpp:21:10: warning: unused variable 'INF' [-Wunused-const-variable]
const ll INF = 0x3f3f3f3f3f3f3f3f;
         ^
./Main.cpp:23:10: warning: unused variable 'mod' [-Wunused-const-variable]
const ll mod = 998244353;
         ^
7 warnings generated.

Judge Result