제출 #940623

#제출 시각아이디문제언어결과실행 시간메모리
940623Der_Vlapos미술 수업 (IOI13_artclass)C++17
0 / 100
68 ms31312 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair<int, int> #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #include "artclass.h" vector<int> dx = {0, 0, 1, -1}; vector<int> dy = {-1, 1, 0, 0}; vector<vector<int>> was, r, g, b; int n, m; bool good(int x, int y) { return x >= 0 and y >= 0 and x < n and y < m; } int dfs1(int x, int y) { assert(x < n); assert(y < m); assert(!was[x][y]); assert(x >= 0); assert(y >= 0); was[x][y] = 1; int sz = 1; for (int d = 0; d < 4; ++d) { int tox = x + dx[d]; int toy = y + dy[d]; if (good(tox, toy) and !was[tox][toy]) { assert(tox < n and toy < m); int diff = abs(r[x][y] - r[tox][toy]) + abs(g[x][y] - g[tox][toy]) + abs(b[x][y] - b[tox][toy]); if (diff <= 200) sz += dfs1(tox, toy); } } return sz; } int dfs2(int x, int y) { was[x][y] = 1; int sz = 1; for (int d = 0; d < 4; ++d) { int tox = x + dx[d]; int toy = y + dy[d]; if (good(tox, toy) and !was[tox][toy]) { int diff = abs(r[x][y] - r[tox][toy]) + abs(g[x][y] - g[tox][toy]) + abs(b[x][y] - b[tox][toy]); if (diff <= 60) sz += dfs2(tox, toy); } } return sz; } int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) { was.resize(H + 100, vector<int>(W + 100)); r.resize(H + 100, vector<int>(W + 100)); g.resize(H + 100, vector<int>(W + 100)); b.resize(H + 100, vector<int>(W + 100)); n = H; m = W; vector<int> d; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { r[i][j] = R[i][j]; g[i][j] = G[i][j]; b[i][j] = B[i][j]; } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (!was[i][j]) d.pb(dfs1(i, j)); sort(all(d)); reverse(all(d)); if ((int)d.size() == 1) return 4; if (d[0] + d[1] >= (double)(n * m) * 0.60) return 4; // cout << d[0] << " " << d[1] << ": " << (double)(n * m) * 0.60 << "!\n"; d.clear(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) was[i][j] = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (!was[i][j]) d.pb(dfs2(i, j)); if (((double)d.size() / (double)(H * W)) <= 0.3) return 1; if (((double)d.size() / (double)(H * W)) >= 0.7) return 3; return 2; } // #include <stdio.h> // #include "artclass.h" // #include <assert.h> // static int DIM[2]; // static int R[500][500]; // static int G[500][500]; // static int B[500][500]; // int main() // { // assert(scanf("%d", &DIM[1]) == 1); // assert(scanf("%d", &DIM[0]) == 1); // for (int i = 0; i < DIM[0]; i++) // for (int j = 0; j < DIM[1]; j++) // assert(scanf("%d %d %d", &R[i][j], &G[i][j], &B[i][j]) == 3); // printf("%d\n", style(DIM[0], DIM[1], R, G, B)); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...