ログイン
新規登録
AtsuoCoder Optimization Contest 001
読込中…
Home
Tasks
Clar
Submissions
Standings
提出 75d9daec-69e5-40a8-907e-d5caff236fd1
コード
#ifndef INCLUDE_MACRO #define INCLUDE_MACRO #include __FILE__ // 山登りに行こう! random_device get_rand; int N, T; vector<vector<int>> A(60, vector<int>(60)); vector<vector<int>> B(60, vector<int>(60)); vector<int> H(3000), W(3000), from(3000, -1), to(3000), rule_count(3000), output_rule, X, Y; vector<pair<int, int>> HW_larger(3000); void heat(Timer timer) { for (auto p : HW_larger) { int i = p.second; // 使うルールはi番目 int best_before_score = -1, best_after_score = -1, best_x = -1, best_y = -1; vector<vector<int>> BA(N + 1, vector<int>(N + 1, 0)); vector<vector<int>> Bto(N + 1, vector<int>(N + 1, 0)); double heat_x; bool change_x; rep(h, N) { rep(w, N) { BA[h + 1][w + 1] = BA[h + 1][w] + (B[h][w] - A[h][w]) * (B[h][w] - A[h][w]); if (A[h][w] == from[i]) Bto[h + 1][w + 1] = Bto[h + 1][w] + (B[h][w] - to[i]) * (B[h][w] - to[i]); else Bto[h + 1][w + 1] = Bto[h + 1][w] + (B[h][w] - A[h][w]) * (B[h][w] - A[h][w]); } } rep(h, N) { rep(w, N) { BA[h + 1][w + 1] += BA[h][w + 1]; Bto[h + 1][w + 1] += Bto[h][w + 1]; } } for (int x = 0; x < N - H[i] + 1; x++) { for (int y = 0; y < N - W[i] + 1; y++) { if (!timer.is_under(2.9)) goto FIN; if (rule_count[i] >= 3) goto RE; int before_score = BA[H[i] + x][W[i] + y] - BA[H[i] + x][y] - BA[x][W[i] + y] + BA[x][y]; int after_score = Bto[H[i] + x][W[i] + y] - Bto[H[i] + x][y] - Bto[x][W[i] + y] + Bto[x][y]; if ((before_score - after_score) > (best_before_score - best_after_score)) { best_before_score = before_score; best_after_score = after_score; best_x = x; best_y = y; } } } if (best_x == -1) goto RE; heat_x = best_after_score * 1.5 / best_before_score; change_x = (get_rand() * 1.0 / (1LL << 32) < heat_x); if (change_x) { rule_count[i]++; output_rule.push_back(i); X.push_back(best_x); Y.push_back(best_y); rep(hh, H[i]) { rep(ww, W[i]) { int h = hh + best_x; int w = ww + best_y; if (A[h][w] == from[i]) A[h][w] = to[i]; } } } RE:; } FIN: return; } signed main() { cin >> N >> T; rep(i, N) rep(j, N) cin >> A[i][j]; rep(i, N) rep(j, N) cin >> B[i][j]; rep(i, T) { cin >> H[i] >> W[i] >> from[i] >> to[i]; HW_larger[i] = { H[i] * W[i], i }; } Timer timer; sort(HW_larger.begin(), HW_larger.end()); while (T > 0) { if (!timer.is_under(2.9)) break; heat(timer); } cout << output_rule.size() << endl; rep(i, output_rule.size()) { cout << output_rule[i] << " " << X[i] << " " << Y[i] << endl; } return 0; } #else #include <iostream> // cout, endl, cin #include <string> // string, to_string, stoi #include <vector> // vector #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound #include <utility> // pair, make_pair #include <tuple> // tuple, make_tuple #include <cstdint> // int64_t, int*_t #include <cstdio> // printf #include <cmath> // sqrt #include <map> // map #include <queue> // queue, priority_queue #include <set> // set #include <stack> // stack #include <deque> // deque #include <unordered_map> // unordered_map #include <unordered_set> // unordered_set #include <bitset> // bitset #include <cctype> // isupper, islower, isdigit, toupper, tolower #include <chrono> // Timer #include <iomanip> // setprecision #include <limits> // INT_MAX, LLONG_MAX #include <random> // random using namespace std; #define int long long #define set_dxy4 std::vector<int> dx4(4); dx4 = {1, -1, 0, 0}; std::vector<int> dy4(4); dy4 = {0, 0, 1, -1} #define set_dxy8 std::vector<int> dx8(8); dx8 = {1, -1, 0, 0, 1, -1, -1, 1}; std::vector<int> dy8(8); dy8 = {0, 0, 1, -1, 1, -1, 1, -1} #define under(N) std::fixed << std::setprecision(N) #define all(x) x.begin(), x.end() #define rep(i, n) for (int i = 0; i < n; i++) #define orep(i, n) for (int i = 1; i <= n; i++) #define intmod const int mod = 998244353 #define INF (1LL<<60)*3 template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int ipow(int x, int y) { int ret = 1; while (y > 0) { if (y % 2 == 1) { ret *= x; } x *= x; y >>= 1; } return ret; } int mod_pow(int x, int y, int mod) { int ret = 1; while (y > 0) { if (y % 2 == 1) { ret = ret * x % mod; } x = x * x % mod; y >>= 1; } return ret; } unsigned int isqrt(unsigned int n) { if (n == 0) return 0; unsigned int rinzi = (unsigned int)(std::sqrt(n)) - 1; return rinzi * (rinzi + 2) < n ? rinzi + 1 : rinzi; } bool out_glid(int i, int j, int h, int w) { if (i < 0 || h <= i || j < 0 || w <= j) return true; else return false; } class Timer { chrono::system_clock::time_point start; public: Timer() : start(chrono::system_clock::now()) {} double count() { chrono::duration<double> Time_ = chrono::system_clock::now() - start; return Time_.count(); } bool is_under(double x) { return (this->count()) < x; } }; template<class T> void allout(T x) { for (auto it = x.begin(); it != x.end(); it++) { std::cout << *it << " "; } std::cout << std::endl; } template<> void allout(std::map<int, int> x) { for (auto it = x.begin(); it != x.end(); it++) { std::cout << (*it).first << " " << (*it).second << "\n"; } } template<> void allout(std::map<int, std::set<int>> x) { for (auto it = x.begin(); it != x.end(); it++) { std::cout << (*it).first << "\n"; allout((*it).second); } } template<> void allout(std::vector<std::vector<int>> x) { for (auto it = x.begin(); it != x.end(); it++) { allout(*it); } } template<> void allout(std::vector<std::string> x) { for (auto it = x.begin(); it != x.end(); it++) { std::cout << *it << "\n"; } } #endif
結果
問題
点数
言語
結果
実行時間
メモリ
A - Replace() は Replace() されました
151259720
C++
AC
2929 ms
4324 KiB