Submission #1075973

#TimeUsernameProblemLanguageResultExecution timeMemory
1075973shmaxArt Class (IOI13_artclass)C++17
84 / 100
55 ms8788 KiB
#include "artclass.h" #include <bits/stdc++.h> using namespace std; template<typename T> using vec = vector<T>; typedef struct { int r, g, b; } RGB; double ColourDistance(RGB e1, RGB e2) { long rmean = ((long) e1.r + (long) e2.r) / 2; long r = (long) e1.r - (long) e2.r; long g = (long) e1.g - (long) e2.g; long b = (long) e1.b - (long) e2.b; return sqrt((((512 + rmean) * r * r) >> 8) + 4 * g * g + (((767 - rmean) * b * b) >> 8)); } int style(int N, int M, int R[500][500], int G[500][500], int B[500][500]) { map<tuple<int, int, int>, int> colors; vec<vec<tuple<int, int, int>>> mtr(N, vec<tuple<int, int, int>>(M)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // colors.insert(fix_color(R[i][j], G[i][j], B[i][j])); mtr[i][j] = tuple<int, int, int>(R[i][j], G[i][j], B[i][j]); } } vec<vec<bool>> used(N, vec<bool>(M, false)); int cnt = 0; int most_common = 0; int kd = 50; auto similar = [&](tuple<int, int, int> a, tuple<int, int, int> b) { int r1, g1, b1, r2, g2, b2; tie(r1, g1, b1) = a; tie(r2, g2, b2) = b; return ColourDistance({r1, g1, b1}, {r2, g2, b2}) < kd; }; for (int i = 0; i < N; i++) { for (int j = 0; j < M - 1; j++) { cnt += !similar(mtr[i][j], mtr[i][j + 1]); } } // cout << cnt << endl; if (cnt < 3500) { return 4; } if (cnt > 80000) { return 3; } if (cnt < 20000) { return 1; } return 2; // mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); // // auto BFS = [&](int i, int j) { // if (used[i][j]) return; // cnt++; // int sz = 1; // queue<pair<int, int>> q; // q.push({i, j}); // used[i][j] = true; // while (!q.empty()) { // auto [x, y] = q.front(); // q.pop(); // sz++; // for (int dx = -1; dx <= 1; dx++) { // for (int dy = -1; dy <= 1; dy++) { // if (dx == 0 && dy == 0) continue; // int nx = x + dx; // int ny = y + dy; // if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // if (used[nx][ny]) continue; // if (!similar(mtr[i][j], mtr[nx][ny])) continue; // used[nx][ny] = true; // q.push({nx, ny}); // } // } // } // most_common = max(most_common, sz); // }; // for (int i = 0; i < N; i++) { // for (int j = 0; j < M; j++) { // BFS(i, j); // } // } // // // cout << most_common << " " << cnt << endl; // if (cnt > 2200) return 3; // if (cnt < 380) return 4; // if (most_common < 111036) return 1; // return 2; // if (cnt < 3900) { // return 4; // } // if (cnt < 4200) { // if (rnd() % 2 == 0) return 1; // else return 4; // } else { // if (rnd() % 2 == 0) return 2; // else return 3; // } // set<int> s; // int n = 8; // mt19937 rnd(228); // map<tuple<int, int, int>, int> rnd_m; // for (int i = 0; i < N - n; i++) { // for (int j = 0; j < M - n; j++) { // set<tuple<int, int, int>> cur; // for (int k = 0; k < n; k++) { // for (int l = 0; l < n; l++) { // cur.insert(mtr[i + k][j + l]); // } // } // int hash = 0; // for (auto &color: cur) { // if (rnd_m.find(color) == rnd_m.end()) { // rnd_m[color] = rnd(); // } // hash = hash * 228 + rnd_m[color]; // } // // s.insert(hash); // } // } // // int most_common = 0; // cout << colors. // // size() // // << " " << most_common << " " << s. // // size() // // << // endl; }

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:33:9: warning: unused variable 'most_common' [-Wunused-variable]
   33 |     int most_common = 0;
      |         ^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...