제출 #533665

#제출 시각아이디문제언어결과실행 시간메모리
533665rumen_mAliens (IOI16_aliens)C++17
4 / 100
1898 ms472 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...