Submission #1260489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260489		repmann	Art Class (IOI13_artclass)	C++20	0 / 100	45 ms	17472 KiB

artclass

#include <bits/stdc++.h>
#include "artclass.h"
using namespace std;
const int T = 6000;
int N, M, comp;
int r0, g0, b0;
int V[502][502];
int R[502][502], G[502][502], B[502][502];
int R1[502][502], G1[502][502], B1[502][502];
int di[8] = {-1, +0, +1, +0, -1, -1, +1, +1};
int dj[8] = {+0, -1, +0, +1, -1, +1, +1, -1};
inline int sqr(int x) {return x * x;}
inline int dist(int r1, int g1, int b1, int r2, int g2, int b2) {return sqr(r1 - r2) + sqr(g1 - g2) + sqr(b1 - b2);}
inline void Blur(int K)
{
  int sumR = 0, sumG = 0, sumB = 0;
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      sumR = sumG = sumB = 0;
      for(int k = max(1, i - K); k <= min(N, i + K); k++)
      {
        for(int l = max(1, j - K); l <= min(M, j + K); l++)
        {
          sumR += R[k][l];
          sumG += G[k][l];
          sumB += B[k][l];
        }
      }
      R1[i][j] = sumR / ((K + 1) * (K + 1));
      G1[i][j] = sumG / ((K + 1) * (K + 1));
      B1[i][j] = sumB / ((K + 1) * (K + 1));
    }
  }
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      R[i][j] = R1[i][j];
      G[i][j] = G1[i][j];
      B[i][j] = B1[i][j];
    }
  }
  return;
}
inline void DFS(int i, int j)
{
  V[i][j] = comp;
//  for(int k = 0; k < 8; k++)
  for(int k = 0; k < 4; k++)
  {
    if(V[i + di[k]][j + dj[k]]) continue;
//    if(dist(R[i][j], G[i][j], B[i][j], R[i + di[k]][j + dj[k]], G[i + di[k]][j + dj[k]], B[i + di[k]][j + dj[k]]) > T) continue;
    if(dist(r0, g0, b0, R[i + di[k]][j + dj[k]], G[i + di[k]][j + dj[k]], B[i + di[k]][j + dj[k]]) > T) continue;
    DFS(i + di[k], j + dj[k]);
  }
  return;
}
inline void DFS1(int i, int j)
{
  V[i][j] = comp;
  for(int k = 0; k < 8; k++)
  {
    if(V[i + di[k]][j + dj[k]]) continue;
    if(dist(R[i][j], G[i][j], B[i][j], R[i + di[k]][j + dj[k]], G[i + di[k]][j + dj[k]], B[i + di[k]][j + dj[k]]) > T) continue;
    DFS1(i + di[k], j + dj[k]);
  }
  return;
}
inline bool detect4()
{
  memset(V, 0, sizeof(V));
  comp = 0;
  for(int i = N + 1; i >= 0; i--) V[i][0] = V[i][M + 1] = -1;
  for(int j = M + 1; j >= 0; j--) V[0][j] = V[N + 1][j] = -1;
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      if(V[i][j]) continue;
      comp++;
      r0 = R[i][j];
      g0 = G[i][j];
      b0 = B[i][j];
      DFS(i, j);
      if(comp > 12) return false;
    }
  }
  return true;
}
int style(int n, int m, int r[500][500], int g[500][500], int b[500][500])
{
  N = n;
  M = m;
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      R[i][j] = r[i - 1][j - 1];
      G[i][j] = g[i - 1][j - 1];
      B[i][j] = b[i - 1][j - 1];
    }
  }
  if(detect4()) return 4;
  memset(V, 0, sizeof(V));
  for(int i = N + 1; i >= 0; i--) V[i][0] = V[i][M + 1] = -1;
  for(int j = M + 1; j >= 0; j--) V[0][j] = V[N + 1][j] = -1;
//  Blur(3);
  comp = 0;
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      if(V[i][j]) continue;
      comp++;
      DFS1(i, j);
    }
  }
  cout << comp << '\n';
  if(comp <= 10) return 2;
  if(comp <= 70) return 1;
  return 3;
  exit(333);
}
//int n, m, r[500][500], g[500][500], b[500][500];
//int main()
//{
//  freopen("style-1-1.txt", "r", stdin);
////  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//  cin >> n >> m;
//  for(int i = 0; i < n; i++)
//  {
//    for(int j = 0; j < m; j++) cin >> r[i][j] >> b[i][j] >> b[i][j];
//  }
//  cout << style(n, m, r, g, b) << '\n';
//  return 0;
//}

• Subtask 1: 0 / 100