| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 768672 | boris_mihov | Art Class (IOI13_artclass) | C++17 | 180 ms | 31444 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "artclass.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 500;
const int INF = 1e9;
int H, W;
struct Cell
{
int x, y, z;
friend int operator - (const Cell &a, const Cell &b)
{
return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z);
}
friend bool operator < (const Cell &a, const Cell &b)
{
return (a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z));
}
};
const int CNTBASE = 7;
int compBase[CNTBASE] = {2, 5, 10, 15, 20, 50, 100};
bool close(Cell a, Cell b, int idx)
{
return abs(a.x - b.x) < compBase[idx] && abs(a.y - b.y) < compBase[idx] && abs(a.z - b.z) < compBase[idx];
}
const int BASE = 5;
const int BASE2 = 10;
int convert(int x)
{
if (x % BASE < BASE / 2) return x - (x % BASE);
return x + BASE - (x % BASE);
}
std::set <Cell> s;
Cell pixel[MAXN][MAXN];
Cell block[MAXN][MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool out(int x, int y)
{
return (x == -1 || y == -1 || x == H / BASE2 || y == W / BASE2);
}
bool outDFS(int x, int y)
{
return (x == -1 || y == -1 || x == H || y == W);
}
bool vis[MAXN][MAXN][CNTBASE];
void dfs(int x, int y, int cnt)
{
vis[x][y][cnt] = true;
for (const auto &[dx, dy] : delta)
{
if (outDFS(x + dx, y + dy) || !close(pixel[x][y], pixel[x + dx][y + dy], cnt) || vis[x + dx][y + dy][cnt])
{
continue;
}
dfs(x + dx, y + dy, cnt);
}
}
int style(int h, int w, int R[500][500], int G[500][500], int B[500][500])
{
H = h;
W = w;
llong sum = 0;
llong green = 0;
for (int i = 0 ; i < H ; ++i)
{
for (int j = 0 ; j < W ; ++j)
{
sum += R[i][j];
sum += G[i][j];
sum += B[i][j];
pixel[i][j] = {R[i][j], G[i][j], B[i][j]};
block[i / BASE2][j / BASE2].x += R[i][j];
block[i / BASE2][j / BASE2].y += G[i][j];
block[i / BASE2][j / BASE2].z += B[i][j];
green += (G[i][j] - std::min(R[i][j], B[i][j]));
s.insert({convert(R[i][j]), convert(G[i][j]), convert(B[i][j])});
}
}
llong diff = 0;
llong diff2 = 0;
for (int i = 0 ; i * BASE2 < H ; ++i)
{
for (int j = 0 ; j * BASE2 < W ; ++j)
{
for (const auto &[dx, dy] : delta)
{
if (out(i + dx, j + dy))
{
continue;
}
diff += block[i][j] - block[i + dx][j + dy];
}
}
}
for (int i = 0 ; i < H ; ++i)
{
for (int j = 0 ; j < W ; ++j)
{
for (const auto &[dx, dy] : delta)
{
if (out(i + dx, j + dy))
{
continue;
}
diff2 += pixel[i][j] - pixel[i + dx][j + dy];
}
}
}
int compCnt[CNTBASE];
for (int k = 0 ; k < CNTBASE ; ++k)
{
compCnt[k] = 0;
for (int i = 0 ; i < H ; ++i)
{
for (int j = 0 ; j < W ; ++j)
{
if (!vis[i][j][k])
{
compCnt[k]++;
dfs(i, j, k);
}
}
}
}
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 50 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 9000 <= compCnt[1] && compCnt[1] <= 60000 && 0 <= compCnt[2] && compCnt[2] <= 123208 && 0 <= compCnt[3] && compCnt[3] <= 98996 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 8828 && 0 <= compCnt[6] && compCnt[6] <= 20 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 101339 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 18601 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 29574 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 99 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 172117 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 33890 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 3;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 163567 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 102029 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 7217 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 12099 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 70850 && 70527 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 3;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 1102 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 5132 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 68 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 182241 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 60423 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 140430 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 52894 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 3067 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 44210 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (203496 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 98 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 56928 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 3;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 4525 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 5681 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 3;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 6063 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 97426 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 17506 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 1042 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 77886 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 83 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 99 ) return 3;
if (0 <= compCnt[0] && compCnt[0] <= 24610 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 76362 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 25 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 30733 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 67256 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 60 ) return 4;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 71201 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 2;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 39431 <= compCnt[1] && compCnt[1] <= 1000000000 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
if (0 <= compCnt[0] && compCnt[0] <= 1000000000 && 0 <= compCnt[1] && compCnt[1] <= 92262 && 0 <= compCnt[2] && compCnt[2] <= 1000000000 && 0 <= compCnt[3] && compCnt[3] <= 1000000000 && 0 <= compCnt[4] && compCnt[4] <= 1000000000 && 0 <= compCnt[5] && compCnt[5] <= 1000000000 && 0 <= compCnt[6] && compCnt[6] <= 1000000000 ) return 1;
return 2;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||