Submission #33008172

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
#define REP(i, a, n) for (int i = (a); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#ifdef LOCAL
#define ESC_BLACK "\033[30m"
#define ESC_RED "\033[31m"
#define ESC_GREEN "\033[32m"
#define ESC_YELLOW "\033[33m"
#define ESC_BLUE "\033[34m"
#define ESC_MAGENTA "\033[35m"
#define ESC_CYAN "\033[36m"
#define ESC_WHITE "\033[37m"
#define ESC_DEFAULT "\033[39m"
#define ESC_BG_BLACK "\033[40m"
#define ESC_BG_RED "\033[41m"
#define ESC_BG_GREEN "\033[42m"
#define ESC_BG_YELLOW "\033[43m"
#define ESC_BG_BLUE "\033[44m"
#define ESC_BG_MAGENTA "\033[45m"
#define ESC_BG_CYAN "\033[46m"
#define ESC_BG_WHITE "\033[47m"
#define ESC_BG_DEFAULT "\033[49m"
#define ESC_FT_UNDERBAR "\033[4m"
#define ESC_FT_BOLD "\033[1m"
#define ESC_FT_REVERSE "\033[7m"
#define ESC_FT_CLEAR "\033[0m"
// 画面のクリア
void ESC_CLEAR() {
    cerr << "\033[2J" << flush;
}
// (y行目,x列目)にカーソルを移動
void ESC_MOVE(int y, int x) {
    cerr << "\033[" << y << ";" << x << "H" << flush;
}

// 変数名あり
//#define debug(x) cerr << #x << ": " << (x) << endl;
// 行数あり
#define debug(x) cerr << "L" << __LINE__ << " " << #x << ": " << (x) << endl;
// 色あり
//#define debug(x) cerr << ESC_YELLOW << "L" << __LINE__ << " " << #x << ": " << (x) << ESC_DEFAULT
//<< endl;
// ファイル出力
// ofstream logfs("log.txt");
//#define debug(x) logfs << "L" << __LINE__ << " " << #x << ": " << (x) << endl;

// コンテナ出力
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (const auto& x : v) os << " " << x;
    os << " ]";
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    // os << "[";
    // for(const auto& e: v) os << " " << e;
    // os << " ]";
    for (size_t i = 0; i < v.size(); i++) {
        os << endl;
        for (size_t j = 0; j < v[i].size(); j++) {
            // os << v[i][j];
            os << setw(3) << v[i][j];
        }
    }
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
    os << "[";
    for (const auto& x : v) os << " " << x;
    os << " ]";
    return os;
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& v) {
    os << "[";
    for (const auto& x : v) os << " " << x;
    os << " ]";
    return os;
}
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& m) {
    os << "{";
    for (const auto& x : m) os << " " << x.first << ":" << x.second;
    os << " }";
    return os;
}

#else
#define debug(x)
#endif

class Timer {
    std::chrono::system_clock::time_point start_time;
    std::chrono::system_clock::time_point getNow() {
        return std::chrono::system_clock::now();
    }

   public:
    void start() {
        start_time = getNow();
    }
    float getSec() {
        float count =
            std::chrono::duration_cast<std::chrono::microseconds>(getNow() - start_time).count();
        return count / 1e6;
    }
};

uint32_t xor128() {
    static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    uint32_t t;
    t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
inline float frand() {
    return xor128() % UINT32_MAX / static_cast<float>(UINT32_MAX);
}

struct P {
    int x, y;
    P() : x(0), y(0) {
    }
    P(int x, int y) : x(x), y(y) {
    }
};
ostream& operator<<(ostream& os, const P& p) {
    os << "(" << p.x << "," << p.y << ")";
    return os;
}

// 座圧
struct CoordComp {
    unordered_map<int, int> z2id;
    vector<int> id2z;

    void add(int x) {
        z2id[x] = 1;
    }
    void init() {
        for (auto& pr : z2id) {
            id2z.push_back(pr.first);
        }
        sort(id2z.begin(), id2z.end());
        for (int i = 0; i < id2z.size(); i++) {
            z2id[id2z[i]] = i;
        }
    }
    int get_id(int x) {
        return z2id[x];
    }
    int get_z(int id) {
        return id2z[id];
    }
};

// 2次元累積和
template <class T>
struct SummedAreaTable {
    int N;
    vector<vector<T>> table;

    SummedAreaTable(int N) : N(N), table(N, vector<T>(N, 0)) {
    }
    void add(int y, int x) {
        table[y][x]++;
    }
    void init() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                table[i][j] += get(i, j - 1) + get(i - 1, j) - get(i - 1, j - 1);
            }
        }
    }
    // [0,y]と[0,x]の領域の個数を返す
    T get(int y, int x) {
        if (y < 0 || x < 0) return 0;
        if (y >= N) y = N - 1;
        if (x >= N) x = N - 1;
        return table[y][x];
    }
    // [y1,y2)と[x1,x2)の領域の個数を返す
    T get(int y1, int x1, int y2, int x2) {
        return get(y2 - 1, x2 - 1) - get(y1 - 1, x2 - 1) - get(y2 - 1, x1 - 1) +
               get(y1 - 1, x1 - 1);
    }
};

class Solver {
    //
    static constexpr int C_INF = 100000;
    static constexpr int MAXN = 5505;
    static constexpr int MAXD = 10;
    //
    static constexpr float TIME_LIMIT = 2.9;
    static constexpr double START_TEMP = 2000.0;
    static constexpr double END_TEMP = 1e-10;

    Timer timer;
    int N, K;
    vector<int> expect;               // 期待人数
    int expect_sum;                   // 期待人数の合計
    vector<P> ichigo;                 // いちごの情報
    CoordComp comp_x, comp_y;         // 座圧
    SummedAreaTable<uint16_t> table;  // 累積和テーブル

    // 状態
    vector<int> xs, ys;  // 各直線(座圧後のindexを保持)
    vector<int> actual;  // 現在の人数
    ll score;            // 現在のスコア

    // ベスト解
    vector<int> best_xs, best_ys;
    vector<int> best_actual;
    ll best_score;

    void update_score() {
        score = 0;
        ll esum = 0;
        REP(i, 1, 11) {
            esum += (i / 2.5 + 1) * expect[i];
            score += 1000000LL * (i / 2.5 + 1) * min(expect[i], actual[i]);
        }
        score /= esum;
    }

    void init() {
        // 座圧と累積和テーブルのfinalize処理
        comp_x.add(-C_INF);
        comp_x.add(C_INF);
        comp_y.add(-C_INF);
        comp_y.add(C_INF);
        comp_x.init();
        comp_y.init();
        rep(i, N) {
            int zy = comp_y.get_id(ichigo[i].y);
            int zx = comp_x.get_id(ichigo[i].x);
            table.add(zy, zx);
        }
        table.init();

        // 期待人数の合計
        expect_sum = 0;
        REP(i, 1, 11) expect_sum += expect[i];

        // 初期状態の作成
        rep(i, 90) {
            xs.push_back(i * (comp_x.id2z.size() / 90));
        }
        rep(i, 10) {
            ys.push_back(i * (comp_y.id2z.size() / 10));
        }

        REP(i, -1, ys.size()) {
            REP(j, -1, xs.size()) {
                int y1 = (i >= 0) ? ys[i] : -1;
                int x1 = (j >= 0) ? xs[j] : -1;
                int y2 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;
                int x2 = (j + 1 < xs.size()) ? xs[j + 1] : MAXN + 1;
                uint16_t num = table.get(y1, x1, y2, x2);
                if (1 <= num && num <= 10) {
                    actual[num]++;
                }
            }
        }
        update_score();

        // ベスト解の初期化
        best_score = score;
        best_ys = ys;
        best_xs = xs;
    }

    // 答えの出力
    void output_answer() {
        int k = 0;
        rep(i, best_xs.size()) k++;
        rep(i, best_ys.size()) k++;
        cout << k << endl;
        rep(i, best_xs.size()) {
            cout << comp_x.get_z(best_xs[i]) - 1 << " " << -C_INF << " " << comp_x.get_z(best_xs[i])
                 << " " << C_INF << endl;
        }
        rep(i, best_ys.size()) {
            cout << -C_INF << " " << comp_y.get_z(best_ys[i]) << " " << C_INF << " "
                 << comp_y.get_z(best_ys[i]) - 1 << endl;
        }
    }
    void output_state() {
        int k = 0;
        rep(i, xs.size()) k++;
        rep(i, ys.size()) k++;
        cout << k << endl;
        rep(i, xs.size()) {
            cout << comp_x.get_z(xs[i]) - 1 << " " << -C_INF << " " << comp_x.get_z(xs[i]) << " "
                 << C_INF << endl;
        }
        rep(i, ys.size()) {
            cout << -C_INF << " " << comp_y.get_z(ys[i]) << " " << C_INF << " "
                 << comp_y.get_z(ys[i]) - 1 << endl;
        }
    }

    ////////////////////////////////////////////////////////////////////
    // 近傍、Undo処理
    vector<int> prev_xs, prev_ys;
    vector<int> prev_actual;
    ll prev_score;

    int move_neighbor() {
        prev_xs = xs;
        prev_ys = ys;
        prev_actual = actual;
        prev_score = score;

        int p = xor128() % 100;
        if (p < 96 * 0.9) {  // ずらす：x側を変える
            int r = xor128() % xs.size();
            int d = xor128() % 5 + 1;
            int nx = 0;
            if (xor128() % 2 == 0) {  // 正方向にずらす
                if (r + 1 < xs.size() && xs[r] + d >= xs[r + 1]) return 0;
                if (xs[r] + d >= comp_x.id2z.size()) return 0;
                nx = xs[r] + d;
            } else {  // 負方向にずらす
                if (r - 1 >= 0 && xs[r] - d <= xs[r - 1]) return 0;
                if (xs[r] - d < 0) return 0;
                nx = xs[r] - d;
            }

            REP(i, -1, ys.size()) {
                int y1 = (i >= 0) ? ys[i] : -1;
                int y2 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;
                int x1 = (r - 1 >= 0) ? xs[r - 1] : -1;
                int x2 = xs[r];
                int x3 = (r + 1 < xs.size()) ? xs[r + 1] : MAXN + 1;

                uint16_t num;
                num = table.get(y1, x1, y2, x2);
                if (1 <= num && num <= 10) {
                    actual[num]--;
                }
                num = table.get(y1, x2, y2, x3);
                if (1 <= num && num <= 10) {
                    actual[num]--;
                }
                num = table.get(y1, x1, y2, nx);
                if (1 <= num && num <= 10) {
                    actual[num]++;
                }
                num = table.get(y1, nx, y2, x3);
                if (1 <= num && num <= 10) {
                    actual[num]++;
                }
            }
            xs[r] = nx;
        } else if (p < 96) {  // ずらす：y側を変える
            int r = xor128() % ys.size();
            int d = xor128() % 5 + 1;
            int ny = 0;
            if (xor128() % 2 == 0) {  // 正方向にずらす
                if (r + 1 < ys.size() && ys[r] + d >= ys[r + 1]) return 0;
                if (ys[r] + d >= comp_y.id2z.size()) return 0;
                ny = ys[r] + d;
            } else {  // 負方向にずらす
                if (r - 1 >= 0 && ys[r] - d <= ys[r - 1]) return 0;
                if (ys[r] - d < 0) return 0;
                ny = ys[r] - d;
            }

            REP(i, -1, xs.size()) {
                int x1 = (i >= 0) ? xs[i] : -1;
                int x2 = (i + 1 < xs.size()) ? xs[i + 1] : MAXN + 1;
                int y1 = (r - 1 >= 0) ? ys[r - 1] : -1;
                int y2 = ys[r];
                int y3 = (r + 1 < ys.size()) ? ys[r + 1] : MAXN + 1;

                uint16_t num;
                num = table.get(y1, x1, y2, x2);
                if (1 <= num && num <= 10) {
                    actual[num]--;
                }
                num = table.get(y2, x1, y3, x2);
                if (1 <= num && num <= 10) {
                    actual[num]--;
                }
                num = table.get(y1, x1, ny, x2);
                if (1 <= num && num <= 10) {
                    actual[num]++;
                }
                num = table.get(ny, x1, y3, x2);
                if (1 <= num && num <= 10) {
                    actual[num]++;
                }
            }
            ys[r] = ny;
        } else if (p < 98) {            // 追加
            if (xor128() % 100 < 60) {  // x側に追加
                if (xs.size() >= 90) return 0;
                int r = xor128() % (xs.size() + 1) - 1;
                int x1 = (r >= 0) ? xs[r] : -1;
                int x3 = (r + 1 < xs.size()) ? xs[r + 1] : comp_x.get_id(C_INF);
                if (x3 - x1 <= 2) return 0;
                int x2 = xor128() % (x3 - (x1 + 1)) + x1 + 1;
                REP(i, -1, ys.size()) {
                    int y1 = (i >= 0) ? ys[i] : -1;
                    int y3 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;

                    uint16_t num;
                    num = table.get(y1, x1, y3, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y1, x1, y3, x2);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                    num = table.get(y1, x2, y3, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                }
                xs.push_back(-1);
                for (int i = xs.size() - 1; i > r + 1; i--) {
                    xs[i] = xs[i - 1];
                }
                xs[r + 1] = x2;
            } else {  // y側に追加
                if (ys.size() >= 10) return 0;
                int r = xor128() % (ys.size() + 1) - 1;
                int y1 = (r >= 0) ? ys[r] : -1;
                int y3 = (r + 1 < ys.size()) ? ys[r + 1] : comp_y.get_id(C_INF);
                if (y3 - y1 <= 2) return 0;
                int y2 = xor128() % (y3 - (y1 + 1)) + y1 + 1;
                REP(i, -1, xs.size()) {
                    int x1 = (i >= 0) ? xs[i] : -1;
                    int x3 = (i + 1 < xs.size()) ? xs[i + 1] : MAXN + 1;

                    uint16_t num;
                    num = table.get(y1, x1, y3, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y1, x1, y2, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                    num = table.get(y2, x1, y3, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                }
                ys.push_back(-1);
                for (int i = ys.size() - 1; i > r + 1; i--) {
                    ys[i] = ys[i - 1];
                }
                ys[r + 1] = y2;
            }
        } else {                        // 削除
            if (xor128() % 100 < 60) {  // x側を削除
                if (xs.size() == 1) return 0;
                int r = xor128() % xs.size();
                REP(i, -1, ys.size()) {
                    int y1 = (i >= 0) ? ys[i] : -1;
                    int y2 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;
                    int x1 = (r - 1 >= 0) ? xs[r - 1] : -1;
                    int x2 = xs[r];
                    int x3 = (r + 1 < xs.size()) ? xs[r + 1] : MAXN + 1;

                    uint16_t num;
                    num = table.get(y1, x1, y2, x2);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y1, x2, y2, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y1, x1, y2, x3);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                }
                REP(i, r, xs.size() - 1) {
                    xs[i] = xs[i + 1];
                }
                xs.pop_back();
            } else {  // y側を削除
                if (ys.size() == 1) return 0;
                int r = xor128() % ys.size();

                REP(i, -1, xs.size()) {
                    int x1 = (i >= 0) ? xs[i] : -1;
                    int x2 = (i + 1 < xs.size()) ? xs[i + 1] : MAXN + 1;
                    int y1 = (r - 1 >= 0) ? ys[r - 1] : -1;
                    int y2 = ys[r];
                    int y3 = (r + 1 < ys.size()) ? ys[r + 1] : MAXN + 1;

                    uint16_t num;
                    num = table.get(y1, x1, y2, x2);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y2, x1, y3, x2);
                    if (1 <= num && num <= 10) {
                        actual[num]--;
                    }
                    num = table.get(y1, x1, y3, x2);
                    if (1 <= num && num <= 10) {
                        actual[num]++;
                    }
                }
                REP(i, r, ys.size() - 1) {
                    ys[i] = ys[i + 1];
                }
                ys.pop_back();
            }
        }

        update_score();

        return score - prev_score;
    }

    void move_undo() {
        xs = prev_xs;
        ys = prev_ys;
        actual = prev_actual;
        score = prev_score;
    }
    ////////////////////////////////////////////////////////////////////

    // ベスト解の更新
    void update_best() {
        if (score > best_score) {
            best_score = score;
            best_actual = actual;
            best_ys = ys;
            best_xs = xs;
        }
    }

    // 温度計算
    double calc_temp(double sec) {
        return START_TEMP + (END_TEMP - START_TEMP) * sec / TIME_LIMIT;
    }

   public:
    Solver(int N, int K) : N(N), K(K), expect(MAXD + 1, 0), table(MAXN), actual(MAXD + 1, 0) {
        timer.start();
    }
    void set_expect(int d, int a) {
        expect[d] = a;
    }
    void add_ichigo(int x, int y) {
        ichigo.emplace_back(x, y);
        comp_x.add(x);
        comp_y.add(y);
    }

    ll get_score() const {
        ll ret = 0;
        REP(i, 1, 11) ret += 1000000LL * min(expect[i], best_actual[i]);
        ret /= expect_sum;
        return ret;
    }

    void solve() {
        init();

        float sec;
        float T;
        int step = 0;
        while (true) {
            step++;
            sec = timer.getSec();
            if (sec > TIME_LIMIT) break;
            T = calc_temp(sec);

            bool undo = false;
            int delta = move_neighbor();

            if (delta < 0) {
                if (exp(delta / T) >= frand()) {
                    ;
                } else {
                    undo = true;
                }
            }
            if (undo) {
                move_undo();
            } else {
                update_best();
            }

            /*
            if (step % 100000 == 1) {
                cerr << "score"
                     << "\t" << score << endl;
                // debug(actual);
                output_state();
            }
            */
        }
        debug(step);
        debug(best_score);
        output_answer();
    }
};

int main() {
    int N, K;
    cin >> N >> K;

    Solver solver(N, K);

    rep(i, 10) {
        int a;
        cin >> a;
        solver.set_expect(i + 1, a);
    }
    vector<P> ichigo(N);

    rep(i, N) {
        int x, y;
        cin >> x >> y;
        solver.add_ichigo(x, y);
    }

    solver.solve();

    cerr << solver.get_score() << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘void CoordComp::init()’:
./Main.cpp:160:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  160 |         for (int i = 0; i < id2z.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp: In member function ‘void Solver::init()’:
./Main.cpp:273:33: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  273 |                 int y2 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;
      |                           ~~~~~~^~~~~~~~~~~
./Main.cpp:274:33: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  274 |                 int x2 = (j + 1 < xs.size()) ? xs[j + 1] : MAXN + 1;
      |                           ~~~~~~^~~~~~~~~~~
./Main.cpp: In member function ‘int Solver::move_neighbor()’:
./Main.cpp:337:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  337 |                 if (r + 1 < xs.size() && xs[r] + d >= xs[r + 1]) return 0;
      |                     ~~~~~~^~~~~~~~~~~
./Main.cpp:338:31: warning: comparison of integer expressions of different signedness: ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  338 |                 if (xs[r] + d >= comp_x.id2z.size()) return 0;
./Main.cpp:348:33: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  348 |                 int y2 = (i + 1 < ys.size()) ? ys[i + 1] : MAXN + 1;
      |                           ~~~~~~^~~~~~~~~~~
./Ma...

Judge Result