Submission #20927098

---

Source Code Expand

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

mt19937 rnd;
uniform_real_distribution<> dist01(0.0, 1.0);
double rnd01(){ return dist01(rnd);}

const double TIME_LIMIT = 4950;
double elapsed;
chrono::system_clock::time_point t_start;
void update_time(){
    auto t_now = chrono::system_clock::now();
    elapsed = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}
bool timeover(){ return (elapsed > TIME_LIMIT);}

const int MX = 10000;

int N, X[200], Y[200], R[200];
vector<tuple<int, int, int, int>> ans;
double opt, coef;

double calc_area_rate(int i){
    auto [a, b, c, d] = ans[i];
    double s = (c-a)*(d-b), r = R[i];
    double v = 1-pow(1-min(r, s)/max(r, s), 2);
    return v;
}

double calc_single_score(int i){
    return calc_area_rate(i)*coef;
}

double calculate(){
    double score = 0;
    for(int i=0; i<N; i++){
        double v = calc_area_rate(i);
        score += v;
    }
    score *= coef;
    return score;
}

bool valid(int a, int b, int c, int d, int idx){
    return (0 <= a && c <= MX && 0 <= b && d <= MX && a <= X[idx] && X[idx] < c && b <= Y[idx] && Y[idx] < d);
}

bool cross(int a, int b, int c, int d, int a2, int b2, int c2, int d2){
    return (min(c, c2)-max(a, a2) > 0 && min(d, d2)-max(b, b2) > 0);
}

bool check(int idx){
    auto [a, b, c, d] = ans[idx];
    if(!valid(a, b, c, d, idx)) return false;
    int area = (c-a)*(d-b);
    if(area > R[idx] || area == 0) return false;
    for(int i=0; i<N; i++) if(i != idx){
        auto& [a2, b2, c2, d2] = ans[i];
        if(cross(a, b, c, d, a2, b2, c2, d2)) return false;
    }
    return true;
}

void change1(int idx, int D, int diff){
    auto& [a, b, c, d] = ans[idx];
    if(D == 0){
        a -= diff;
    }else if(D == 1){
        b -= diff;
    }else if(D == 2){
        c += diff;
    }else if(D == 3){
        d += diff;
    }
}

void try_update(){
    int idx = rand() % N;
    int D = rand() % 4;
    int diff = 1;
    double score = opt - calc_single_score(idx);
    change1(idx, D, diff);
    score += calc_single_score(idx);

    if(!check(idx)){
        change1(idx, D, -diff);
        return;
    }

    // calculate

    const int T = 3000;
    double temp = T * (1 - elapsed/TIME_LIMIT);
    double prob = exp((score - opt) / temp);
    if(rnd01() < prob){
        opt = score;
    }else{
        change1(idx, D, -diff);
    }
}

vector<int> changed_idx;
tuple<int, int, int, int> ans_bef[200];

bool check_force(int idx, int D, double& score){
    auto [a, b, c, d] = ans[idx];
    if(!valid(a, b, c, d, idx)) return false;
    int area = (c-a)*(d-b);
    if(area > R[idx] || area == 0) return false;
    for(int i=0; i<N; i++) if(i != idx){
        auto& [a2, b2, c2, d2] = ans[i];
        if(cross(a, b, c, d, a2, b2, c2, d2)){
            changed_idx.push_back(i);
            ans_bef[i] = ans[i];
            score -= calc_single_score(i);
            change1(i, D^2, -1);
            score += calc_single_score(i);
            // assert(!cross(a, b, c, d, a2, b2, c2, d2));
            if(!valid(a2, b2, c2, d2, i)) return false;
        }
    }
    return true;
}

void try_update_force(){
    int idx = rand() % N;
    int D = rand() % 4;
    int diff = 1;

    changed_idx.clear();
    changed_idx.push_back(idx);
    ans_bef[idx] = ans[idx];
    double score = opt - calc_single_score(idx);

    change1(idx, D, diff);
    score += calc_single_score(idx);

    if(!check_force(idx, D, score)){
        for(int i : changed_idx) ans[i] = ans_bef[i];
        return;
    }

    // calculate
    // double score = calculate();
    const int T = 3000;
    double temp = T * (1 - elapsed/TIME_LIMIT);
    double prob = exp((score - opt) / temp);
    if(rnd01() < prob){
        opt = score;
    }else{
        for(int i : changed_idx) ans[i] = ans_bef[i];
    }
}

void try_change_direction(){
    int idx = rand() % N;
    vector<int> ds = {0, 1, 2, 3};
    random_shuffle(ds.begin(), ds.end());

    double score = opt - calc_single_score(idx);
    auto bef = ans[idx];
    ans[idx] = {X[idx], Y[idx], X[idx]+1, Y[idx]+1};
    for(int D : ds){
        for(int v=8192; v>0; v>>=1){
            change1(idx, D, v);
            if(!check(idx)) change1(idx, D, -v);
        }
    }
    score += calc_single_score(idx);

    const int T = 3000;
    double temp = T * (1 - elapsed/TIME_LIMIT);
    double prob = exp((score - opt) / temp);
    if(rnd01() < prob){
        opt = score;
    }else{
        ans[idx] = bef;
    }
}

int main(){
    t_start = chrono::system_clock::now();
    cin >> N;
    ans.resize(N);
    coef = 1e9/N;
    for(int i=0; i<N; i++){
        cin >> X[i] >> Y[i] >> R[i];
        ans[i] = {X[i], Y[i], X[i]+1, Y[i]+1};
    }
    opt = calculate();

    // iterate
    int iter = 0;
    while(!timeover()){
        iter++;
        try_update();
        if(iter % 10000 == 0) update_time();
        if(iter % 10 == 0) try_update_force();
        if(elapsed >= TIME_LIMIT/2 && iter % 1000 == 0) try_change_direction();
    }

    for(int i=0; i<N; i++){
        auto [a, b, c, d] = ans[i];
        printf("%d %d %d %d\n", a, b, c, d);
    }
    // output debug
    calculate();
    cerr << "score: " << int(opt) << endl;
    cerr << "iter: " << iter << endl;
    update_time();
    cerr << "elapsed: " << elapsed << endl;
    return 0;
}

Submission Info

Judge Result