hackercupai/hackercup
Data Preview The data available in this preview contains a 10 row dataset: Sample Dataset ("sample"): This is a subset of the full dataset, containing data from 2023. To view full dataset, download output_dataset.parquet. This contains data from 2011 to 2023. Fields The dataset include the following fields: name (string) year (string) round (string) statement (string) input (string) solution (string) code (string) sample_input (string) sample_output (string)… See the full description on the dataset page: https://huggingface.co/datasets/hackercupai/hackercup.
242.2k
1#include <algorithm>2#include <iostream>3#include <vector>4using namespace std;5 6int N, M;7vector<vector<int>> G;8 9inline bool check(int r, int c) {10 return r >= 0 && c >= 0 && r < N && c < M;11}12 13inline void upd_options(int r, int c, vector<pair<int, int>>& options) {14 options.emplace_back(r, c);15 for (auto [r2, c2] : {pair{r - 2, c}, {r - 1, c}, {r, c - 1}, {r, c - 2}}) {16 if (r2 >= 0 && c2 >= 0) {17 options.emplace_back(r2, c2);18 }19 }20}21 22int count(vector<pair<int, int>>& options) {23 sort(options.begin(), options.end());24 int res = 0;25 for (int i = 0; i < (int)options.size(); i++) {26 if (i > 0 && options[i] == options[i - 1]) {27 continue;28 }29 auto [r, c] = options[i];30 res += (c + 2 >= M) ? 0 : G[r][c] == G[r][c + 1] && G[r][c] == G[r][c + 2];31 res += (r + 2 >= N) ? 0 : G[r][c] == G[r + 1][c] && G[r][c] == G[r + 2][c];32 }33 return res;34}35 36int solve() {37 cin >> N >> M;38 G.assign(N, vector<int>(M));39 for (int i = 0; i < N; i++) {40 for (int j = 0; j < M; j++) {41 cin >> G[i][j];42 }43 }44 vector<vector<int>> b(N, vector<int>(M));45 vector<int> cnts(1 << 7, 0);46 vector<pair<int, int>> options, semi_options;47 int res = 0;48 int skip_same = (N > 4 || M > 4);49 for (int r = 0; r < N; r++) {50 for (int c = 0; c < M; c++) {51 semi_options.clear();52 upd_options(r, c, semi_options);53 for (auto [r2, c2] : {pair{r + 1, c}, {r, c + 1}}) {54 if (!check(r2, c2) || G[r][c] == G[r2][c2]) {55 continue;56 }57 swap(G[r][c], G[r2][c2]);58 options = semi_options;59 upd_options(r2, c2, options);60 b[r][c] = max(b[r][c], count(options));61 swap(G[r][c], G[r2][c2]);62 }63 if (skip_same) {64 res = max(res, b[r][c]);65 }66 cnts[b[r][c]]++;67 }68 }69 int max_cnt = 0;70 for (int i = 0; i < (int)cnts.size(); i++) {71 if (cnts[i]) {72 max_cnt = max(max_cnt, i);73 }74 }75 const int WINSZ = 3;76 for (int r = 0; r < N; r++) {77 for (int c = 0; c < M; c++) {78 if (res == 16) {79 break;80 }81 if (b[r][c] + 8 <= res) {82 continue;83 }84 if (skip_same) {85 bool found = false;86 for (auto [r11, c11] : {pair{r + 1, c}, {r, c + 1}}) {87 if (!check(r11, c11)) {88 continue;89 }90 if (G[r][c] != G[r11][c11]) {91 found = true;92 break;93 }94 }95 if (!found) {96 continue;97 }98 }99 for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {100 for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {101 cnts[b[r2][c2]]--;102 }103 }104 int cur_max = 0;105 for (int i = max_cnt; i > 0; i--) {106 if (cnts[i]) {107 cur_max = i;108 break;109 }110 }111 res = max(res, cur_max + b[r][c]);112 for (auto [r11, c11] : {pair{r + 1, c}, {r, c + 1}}) {113 if (!check(r11, c11) || (skip_same && G[r][c] == G[r11][c11])) {114 continue;115 }116 swap(G[r][c], G[r11][c11]);117 semi_options.clear();118 upd_options(r, c, semi_options);119 upd_options(r11, c11, semi_options);120 for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {121 for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {122 for (auto [r22, c22] : {pair{r2 + 1, c2}, {r2, c2 + 1}}) {123 if (!check(r22, c22) || (skip_same && G[r2][c2] == G[r22][c22])) {124 continue;125 }126 swap(G[r2][c2], G[r22][c22]);127 options = semi_options;128 upd_options(r2, c2, options);129 upd_options(r22, c22, options);130 res = max(res, count(options));131 swap(G[r2][c2], G[r22][c22]);132 }133 }134 }135 swap(G[r][c], G[r11][c11]);136 }137 for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {138 for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {139 cnts[b[r2][c2]]++;140 }141 }142 }143 }144 return res;145}146 147int main() {148 ios_base::sync_with_stdio(false);149 cin.tie(0);150 int T;151 cin >> T;152 for (int t = 1; t <= T; t++) {153 cout << "Case #" << t << ": " << solve() << endl;154 }155 return 0;156}157