Submission #1885681
Source Code Expand
#include <algorithm> #include <cmath> #include <iostream> #include <vector> using namespace std; #define U(v) cerr << #v << ": " << (v) << endl constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; class timer { vector<timer> timers; int n = 0; public: double limit = 9.95; double t = 0; timer() {} timer(int size) : timers(size) {} bool elapses() const { return time() - t > limit; } void measure() { t = time() - t; ++n; } void measure(char id) { timers[id].measure(); } void print() { if (n % 2) measure(); for (int i = 0; i < 128; ++i) { if (timers[i].n) cerr << (char)i << ' ' << timers[i].t << 's' << endl; } cerr << " " << t << 's' << endl; } static double time() { #ifdef LOCAL return __rdtsc() / 3.3e9; #else unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2.8e9; #endif } } timer(128); #include <ctime> class { unsigned y = time(0); //unsigned y = 2463534242; public: unsigned next() { return y ^= (y ^= (y ^= y << 13) >> 17) << 5; } int next(int b) { return next() % b; } int next(int a, int b) { return next(b - a) + a; } double nextDouble(double b = 1) { return b * next() / 4294967296.0; } double nextDouble(double a, double b) { return nextDouble(b - a) + a; } int operator() (int b) { return next(b); } } rando; struct P { int x, y; char score; P() {} P(int x, int y) : x(x), y(y) {} }; int V, E, S; int neighborsSize; pair<pair<short, short>, pair<char, char>> neighbors[20000 * 64]; vector<pair<short, short>> edges; char weight[501][501]; short vs[62][62]; P ps[501]; P bestPs[501]; int eval() { int score = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) score += weight[e.first][e.second]; } return score; } void init() { vector<int> a(S * S); for (int i = 0; i < S * S; ++i) a[i] = i; sort(a.begin(), a.end(), [](int i, int j) { return max(abs(i % S - (S - 1) / 2.0), abs(i / S - (S - 1) / 2.0)) < max(abs(j % S - (S - 1) / 2.0), abs(j / S - (S - 1) / 2.0)); }); random_shuffle(a.begin(), a.begin() + V, rando); for (int i = 0; i < S + 2; ++i) fill_n(vs[i], S + 2, V); for (int i = 0; i < V; ++i) { auto& p = ps[i]; p = { a[i] % S + 1, a[i] / S + 1 }; vs[p.y][p.x] = i; } for (int i = 0; i < V; ++i) { auto& p = ps[i]; p.score = 0; for (int d = 0; d < 8; ++d) p.score += weight[i][vs[p.y + dy[d]][p.x + dx[d]]]; } } void solve() { init(); copy_n(ps, V, bestPs); int score = eval(); int bestScore = score; int ni = -1; const double InitialHeat = edges.size() / (double)V < 3 ? 2.5 : V <= 200 ? 3.5 : 5; const double FinalHeat = edges.size() / (double)V < 3 ? 0.5 : 2; double heat = 0; for (int iter = -1; ; ) { if ((++iter & 0xffff) == 0) { //double p = 1 - iter / 200000000.0; double p = 1 - (timer.time() - timer.t) / timer.limit; if (p < 0) { U(iter); break; } heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat); } short i, j; unsigned x, y; { if (++ni == neighborsSize) ni = 0; auto& n = neighbors[ni]; i = n.first.first; j = n.first.second; x = ps[j].x + n.second.first; y = ps[j].y + n.second.second; j = vs[y][x]; } if (i == j || max(x - 1, y - 1) >= (unsigned)S) continue; auto& p = ps[i]; if (j == V) { int diff = - ps[i].score; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; if (rando.nextDouble() < exp(diff * heat)) { score += diff; swap(vs[p.y][p.x], vs[y][x]); for (int d = 0; d < 8; ++d) { short v = vs[p.y + dy[d]][p.x + dx[d]]; ps[v].score -= weight[i][v]; v = vs[y + dy[d]][x + dx[d]]; ps[v].score += weight[i][v]; } p.score += diff; p.x = x; p.y = y; if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } } else { vs[p.y][p.x] = j; vs[y][x] = i; int diff = - ps[i].score - ps[j].score; for (int d = 0; d < 8; ++d) diff += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; if (rando.nextDouble() < exp(diff * heat)) { score += diff; for (int d = 0; d < 8; ++d) { short v = vs[p.y + dy[d]][p.x + dx[d]]; ps[v].score -= weight[i][v] - weight[j][v]; v = vs[y + dy[d]][x + dx[d]]; ps[v].score += weight[i][v] - weight[j][v]; } ps[i].score = ps[j].score = 0; for (int d = 0; d < 8; ++d) { ps[i].score += weight[i][vs[y + dy[d]][x + dx[d]]]; ps[j].score += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; } swap(p.x, ps[j].x); swap(p.y, ps[j].y); if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } else { vs[p.y][p.x] = i; vs[y][x] = j; } } } copy_n(bestPs, V, ps); //timer.print(); } int main() { timer.measure(); #ifdef LOCAL int type, seed; cin >> type >> seed; #endif cin >> V >> E; for (int i = 0; i < E; ++i) { int a, b, w; cin >> a >> b >> w; --a; --b; if (w != 0) { edges.emplace_back(a, b); for (int i = 0; i < (int)round(sqrt(w)); ++i) { for (int d = 0; d < 8; ++d) { neighbors[neighborsSize++] = { { a, b }, { (char)dx[d], (char)dy[d] } }; neighbors[neighborsSize++] = { { b, a }, { (char)dx[d], (char)dy[d] } }; } } weight[a][b] = weight[b][a] = w; } } random_shuffle(neighbors, neighbors + neighborsSize, rando); cin >> S; S = (int)sqrt(S); { int E; cin >> E; for (int i = 0; i < E; ++i) { int a, b; cin >> a >> b; } } solve(); #ifdef LOCAL int score = 0; int esum = 0; int wsum = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) { score += weight[e.first][e.second]; ++esum; } wsum += weight[e.first][e.second]; } cerr << type * 500 + seed << "\t" << score << "\t" << wsum << "\t" << esum << "\t" << edges.size() << "\t" << V << "\t" << S << endl; #else for (int i = 0; i < V; ++i) { auto& p = ps[i]; cout << i + 1 << ' ' << (p.y - 1) * S + p.x << endl; } #endif return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Problem 1 |
User | wkb89_ |
Language | C++ (Clang 3.8.0) |
Score | 0 |
Code Size | 7993 Byte |
Status | CE |
Compile Error
./Main.cpp:8:1: error: unknown type name 'constexpr' constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; ^ ./Main.cpp:8:11: error: expected unqualified-id constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; ^ ./Main.cpp:9:1: error: unknown type name 'constexpr' constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; ^ ./Main.cpp:9:11: error: expected unqualified-id constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; ^ ./Main.cpp:13:11: warning: in-class initialization of non-static data member is a C++11 extension [-Wc++11-extensions] int n = 0; ^ ./Main.cpp:15:18: warning: in-class initialization of non-static data member is a C++11 extension [-Wc++11-extensions] double limit = 9.95; ^ ./Main.cpp:16:14: warning: in-class initialization of non-static data member is a C++11 extension [-Wc++11-extensions] double t = 0; ^ ./Main.cpp:51:16: warning: in-class initialization of non-static data member is a C++11 extension [-Wc++11-extensions] un...