Submission #1117379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117379		rolandpetrean	미술 수업 (IOI13_artclass)	C++17	40 / 100	105 ms	46956 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;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (vis[i][j]) {
        continue;
      }
      
      ++comps;
      int sz = dfs(dfs, i, j);
      max_sz = max(max_sz, sz);
    }
  }
  
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int green = 0;
  for (int rep = 0; rep < 100; ++rep) {
    int x = rng() % h, y = rng() % w;
    if (a[x][y][1] > 100 && a[x][y][2] < 50) {
      ++green;
    }
  }
  
  //cerr << "Components: " << comps << endl;
  //cerr << "Max size: " << max_sz << endl;
  //cerr << "Green: " << green << endl;
  
  if (comps < 10) {
    return 4;
  }
  if (comps > 200) {
    return 3;
  }
  return rng() % 2 + 1;
}

• Subtask 1: 40 / 100