제출 #1117376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117376		rolandpetrean	미술 수업 (IOI13_artclass)	C++17	40 / 100	112 ms	48204 KiB

artclass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
// #define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;

#include "artclass.h"

using pixel = array<int, 3>;

int style(int h, int w, int r[500][500], int g[500][500], int b[500][500]) {
  vector a(h, vector(w, pixel()));
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      a[i][j] = {r[i][j], g[i][j], b[i][j]};
    }
  }
  
  auto similar = [&](pixel x, pixel y) -> bool {
    int diff = 0;
    for (int i = 0; i < 3; ++i) {
      diff += abs(x[i] - y[i]);
    }
    return (diff < 80);
  };
  
  const int B = 3;
  vector vis(h, vector<bool>(w));
  auto dfs = [&](auto &&self, int x, int y) -> int {
    vis[x][y] = true;
    
    int sz = 1;
    for (int dx = -B; dx <= B; ++dx) {
      for (int dy = -B; dy <= B; ++dy) {
        int x2 = x + dx, y2 = y + dy;
        if (x2 < 0 || y2 < 0 || x2 >= h || y2 >= w || vis[x2][y2] || !similar(a[x][y], a[x2][y2])) {
          continue;
        }
        sz += self(self, x2, y2);
      }
    }
    return sz;
  };
  
  int comps = 0, max_sz = 0;
  double green = 0;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (vis[i][j]) {
        continue;
      }
      green += a[i][j][1] - a[i][j][0] - a[i][j][2];
      
      ++comps;
      int sz = dfs(dfs, i, j);
      max_sz = max(max_sz, sz);
    }
  }
  green /= h * w;
  
  //cerr << "Components: " << comps << endl;
  //cerr << "Max size: " << max_sz << endl;
  //cerr << "Green: " << green << endl;
  
  if (comps < 10) {
    return 4;
  }
  /*if (comps < 30) {
    return 1;
  }*/
  if (comps < 100) {
    return 2;
  }
  return 3;
}

• Subtask 1: 40 / 100