Submission #768655

#TimeUsernameProblemLanguageResultExecution timeMemory
768655boris_mihovArt Class (IOI13_artclass)C++17
0 / 100
156 ms31992 KiB
#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; 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 == MAXN / BASE2 || y == MAXN / BASE2); } bool outDFS(int x, int y) { return (x == -1 || y == -1 || x == MAXN || y == MAXN); } 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]) { llong sum = 0; llong green = 0; for (int i = 0 ; i < MAXN ; ++i) { for (int j = 0 ; j < MAXN ; ++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] > 128); green -= (B[i][j] > 64 || G[i][j] > 64); 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 < MAXN ; ++i) { for (int j = 0 ; j * BASE2 < MAXN ; ++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 < MAXN ; ++i) { for (int j = 0 ; j < MAXN ; ++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 < MAXN ; ++i) { for (int j = 0 ; j < MAXN ; ++j) { if (!vis[i][j][k]) { compCnt[k]++; dfs(i, j, k); } } } } for (int i = 0 ; i < CNTBASE ; ++i) { std::cout << compCnt[i] << ' '; } std::cout << '\n'; if (compCnt[6] > 10) return 3; if (compCnt[6] <= 3 && compCnt[4] < 50) return 4; if (compCnt[1] < 60000 && (compCnt[1] > 9000 || compCnt[4] > 150)) return 1; if (compCnt[6] <= 3 && (compCnt[1] < 9000 || compCnt[4] < 150)) return 4; if (compCnt[6] <= 5 && compCnt[4] < 15000) return 2; return 3; }
#Verdict Execution timeMemoryGrader output
Fetching results...