제출 #298870

#제출 시각아이디문제언어결과실행 시간메모리
298870emil_physmath미술 수업 (IOI13_artclass)C++17
40 / 100
2863 ms5660 KiB
#include "artclass.h" #include <bits/stdc++.h> using namespace std; const int maxN = 500; mt19937 rng(2083469420); inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } #ifdef MANSON #define BUGO(x) cerr << #x << " = " << x << '\n'; #else #define BUGO(x) #endif int n, m; int (*R) [500]; int (*G) [500]; int (*B) [500]; const int stCoord = 100; inline bool OK(int i, int j) { return i >= stCoord && i < n && j >= stCoord && j < m; } inline bool IsGreen(int i, int j) { int r = R[i][j], g = R[i][j], b = B[i][j]; return g + 10 >= max(r, b) && r + 10 >= b && max(r, g) / 1.5 > b; } struct Col { int r, g, b; }; inline bool Sim(const Col& l, const Col& r) { return abs(l.r - r.r) <= 20 && abs(l.g - r.g) <= 20 && abs(l.b - r.b) <= 20 && abs(l.r - r.r) + abs(l.g - r.g) + abs(l.b - r.b) <= 40; } inline bool Sim3(int i, int j, int x, int y) { vector<Col> l, r; for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy) { int X = i + dx, Y = j + dy; if (OK(X, Y)) l.push_back({R[X][Y], G[X][Y], B[X][Y]}); X = x + dx, Y = y + dy; if (OK(X, Y)) r.push_back(Col{R[X][Y], G[X][Y], B[X][Y]}); } for (Col& a: l) for (Col& b: r) if (Sim(a, b)) return true; return false; } bool used[maxN][maxN]; void BFS(int i, int j, vector<pair<int, int>>& res) { queue<pair<int, int>> q; q.push({i, j}); while (q.size()) { tie(i, j) = q.front(); q.pop(); res.push_back({i, j}); used[i][j] = true; for (int di = -1; di <= 1; ++di) for (int dj = -1; dj <= 1; ++dj) { int x = i + di, y = j + dj; if (!OK(x, y) || used[x][y]) continue; int diff = 0, ndiff = 0;; for (auto [i_, j_]: res) { if (ndiff >= 20 || diff) break; if (!Sim3(i_, j_, x, y)) { ++diff; } else ++ndiff; } if (diff) continue; q.push({x, y}); used[x][y] = true; } } } int Solve() { int greens = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) greens += IsGreen(i, j); if (greens >= (n * m) / 2.5) return 2; vector<vector<bool>> ok(n, vector<bool>(m)); vector<pair<int, int>> comp; int comps = 0; vector<int> compsz; for (int i = stCoord; i + 1 < n; ++i) for (int j = stCoord; j + 1 < m; ++j) { if (used[i][j]) continue; #ifdef MANSON cerr << i << ", " << j << '\n'; #endif ++comps; BFS(i, j, comp); compsz.push_back(comp.size()); int mnX = maxN, mxX = 0, mnY = maxN, mxY = 0; unordered_map<int, int> cntx, cnty; for (auto& p: comp) ++cntx[p.first], ++cnty[p.second]; for (auto& p: comp) { if (cntx[p.first] >= sqrt(comp.size()) / 2) { mnX = min(mnX, p.first); mxX = max(mxX, p.first); } if (cnty[p.second] >= sqrt(comp.size()) / 2) { mnY = min(mnY, p.second); mxY = max(mxY, p.second); } } int recS = max(1, mxX - mnX + 1) * max(1, mxY - mnY + 1); if ((double)comp.size() / recS >= 0.75) for (auto [x, y]: comp) ok[x][y] = true; BUGO(comp.size()) BUGO(recS) BUGO((double)comp.size() / recS) comp.clear(); } int oks = 0; for (int i = 0; i < n; ++i) for (int j = 0; j <m; ++j) oks += ok[i][j]; BUGO(oks) BUGO(n * m) BUGO(oks / double(n * m)) BUGO("") BUGO(comps) sort(compsz.begin(), compsz.end(), greater<int>()); int sumsz = 0; for (int i = 0; i < 6 && i < compsz.size(); ++i) sumsz += compsz[i]; BUGO(sumsz) if (sumsz >= (n * m) * 0.5) return 4; if (comps >= (n * m) / 150.) return 3; return oks / double(n * m) >= 0.4 ? 1 : rnd(3, 4); } int style(int n_, int m_, int r_[500][500], int g_[500][500], int b_[500][500]) { n = n_, m = m_; R = r_, G = g_, B = b_; return Solve(); // if (Is1()) return 1; // return 3; }

컴파일 시 표준 에러 (stderr) 메시지

artclass.cpp: In function 'int Solve()':
artclass.cpp:139:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < 6 && i < compsz.size(); ++i)
      |                              ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...