Submission #533665

#	Time	Username	Problem	Language	Result	Execution time	Memory
533665		rumen_m	Aliens (IOI16_aliens)	C++17	4 / 100	1898 ms	472 KiB

aliens

#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#include <cassert>
#include <iostream>
#include <chrono>
#include <map>
#include <random>
using namespace std;

#define eprintf(...) fprintf(stderr, __VA_ARGS__)

typedef long long llong;
const llong linf = 1e13;
const int inf = 1e9;

llong sqr(int x) {
    return 1ll * x * x;
}

chrono::high_resolution_clock::time_point start;
double wallTime() {
    auto cur = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(cur - start).count() / 1e9;
}

const int segs = 1;
const double timeLimit = 1.9;
mt19937 rng(897123654);

inline int rnd(int a, int b) {
    assert(a <= b);
    return uniform_int_distribution<int>(a, b)(rng);
}

vector<int> L, R;

struct state {
    set<int> in;
    vector<int> vout;
    vector<int> vin;
    llong score = 0;
    state(set<int> in) {
        this->in = in;
        vin = vector<int>(in.begin(), in.end());
        int prv = -1;
        int n = (int)L.size();
        score = val(-1, n - 1);
        for (int i = 0; i < n; i++) {
            if (!in.count(i))
                vout.push_back(i);
            else
                score += val(prv, i) + val(i, n - 1) - val(prv, n - 1), prv = i;
        }
    }
    llong val(int a, int b) {
        return sqr(1 + R[b] - L[a + 1]) - ((a != -1 && R[a] - L[a + 1] >= 0) ? sqr(R[a] - L[a + 1] + 1) : 0);
    }
    void mutate(double temp, double norm) {
        int ri = rnd(0, (int)vin.size() - 1);
        int ro = rnd(0, (int)vout.size() - 1);
        int y = vin[ri];
        auto it = in.find(y);
        assert(it != in.end());
        int x = -1, z = (int)R.size() - 1;
        if (it != in.begin()) {
            x = *(--it);
            ++it;
        }
        if (++it != in.end()) {
            z = *it;
        }
        --it;
        llong old_score = score;
        llong delta = 0;
        delta += -val(x, y) - val(y, z) + val(x, z);
        in.erase(it);
        swap(vin[ri], vout[ro]);
        x = -1;
        y = vin[ri];
        z = (int)R.size() - 1;
        auto res = in.insert(y);
        assert(res.second);
        it = res.first;
        if (it != in.begin()) {
            x = *(--it);
            ++it;
        }
        if (++it != in.end()) {
            z = *it;
        }
        --it;
        delta += val(x, y) + val(y, z) - val(x, z);
        llong new_score = old_score + delta;
        static int iter = 0;
        double prob = 1 - delta/(temp * norm * 20);
        if (delta >= 0) {
            if (++iter % 10000 == 0) {
                eprintf("iter = %d, prob = %.5lf\n", iter, prob);
            }
        }
        if (delta < 0 || bernoulli_distribution(prob)(rng)) {
            score = new_score;
        } else {
            in.erase(it);
            swap(vin[ri], vout[ro]);
            in.insert(vin[ri]);
        }
    }
};

long long take_photos(int n, int m, int k, std::vector<int> row, std::vector<int> column) {
    map<int, int> M;
    for (int i = 0; i < n; i++) {
        int x, y;
        x = row[i];
        y = column[i];
        if (x < y)
            swap(x, y);
        if (!M.count(x))
            M[x] = x;
        M[x] = min(M[x], y);
    }
    for (auto pr : M) {
        while (!L.empty() && L.back() >= pr.second)
            L.pop_back(), R.pop_back();
        R.push_back(pr.first);
        L.push_back(pr.second);
    }
    n = L.size();
    k = min(k, n);
    assert(is_sorted(R.begin(), R.end()));
    assert(is_sorted(L.begin(), L.end()));
    vector<int> vec(k - 1);
    for (int i = 0; i < k - 1; i++) {
        vec[i] = rnd(0, n - k);
    }
    llong ans = linf;
    for (int it = 0; it < segs; it++) {
        start = chrono::high_resolution_clock::now();
        double temp1 = 1e2;
        double temp2 = 1e-2;
        vector<int> tmp;
        for (int i = 0; i < n - 1; i++) {
            tmp.push_back(i);
        }
        shuffle(tmp.begin(), tmp.end(), rng);

        state cur(set<int>(tmp.begin(), tmp.begin() + k - 1));
        double init = cur.score;
        shuffle(tmp.begin(), tmp.end(), rng);
        state cur2(set<int>(tmp.begin(), tmp.begin() + k - 1));
        double init2 = cur.score;
        double norm = max(1.0, fabs(init - init2));
        ans = min(ans, (llong)init);
        if (k == 1 || k == n) {
            return ans;
        }
        int iter = 0;
        while (true) {
            double t = wallTime() / (timeLimit / segs);
            if (t > 1)
                break;
            double temp = exp(log(temp1) * (1 - t) + log(temp2) * t);
            cur.mutate(temp, norm);
            if (ans > cur.score) {
                ans = min(ans, cur.score);
                eprintf("iter = %d, ans = %lld\n", iter, ans);
            }
            if (iter % 100000 == 0) {
                eprintf("iter = %d\n", iter);
            }
            ++iter;
        }
    }
    return ans;
}

// BEGIN CUT
/*
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &r[i], &c[i]);
    }
    long long ans = take_photos(n, m, k, r, c);

    // BEGIN SECRET
    puts("098d134608c94f7413faac591054ee35");
    // END SECRET

    printf("%lld\n", ans);
    return 0;
}
*/
// END CUT

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40