Submission #1359961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359961		pcheloveks	미술 수업 (IOI13_artclass)	C++20	52 / 100	283 ms	4360 KiB

artclass

#include "artclass.h"

#include <bits/stdc++.h>

using namespace std;

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    vector < vector < int > > used(H, vector < int >(W, 0));

    int blendingConst = 200;

    vector < pair < int, int > > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    auto dif = [&](pair < int, int > v1, pair < int, int > v2) {
        return abs(R[v1.first][v1.second] - R[v2.first][v2.second]) + 
               abs(G[v1.first][v1.second] - G[v2.first][v2.second]) + 
               abs(B[v1.first][v1.second] - B[v2.first][v2.second]);
    };

    int cc = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(used[i][j] == 0) {
                queue < pair < int, int > > q;
                q.push({i, j});

                cc++;

                while(!q.empty()) {
                    pair < int, int > val = q.front();
                    q.pop();

                    if(used[val.first][val.second] != 0) continue;
                    used[val.first][val.second] = cc;

                    for(int d = 0; d < dir.size(); d++) {
                        pair < int, int > to = { val.first + dir[d].first, val.second + dir[d].second };
                        
                        if(to.first < 0 || to.second < 0) continue;
                        if(to.first >= H || to.second >= W) continue;

                        if(dif(val, to) <= blendingConst) q.push(to);
                    }
                }
            }
        }
    }

    //cout << cc << endl;
    if(cc >= 70) return 3;
    else if(cc <= 7) {
        int res = 0;


        blendingConst = 70;
        used.clear();
        used.resize(H, vector < int >(W, 0));

        cc = 0;
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                if(used[i][j] == 0) {
                    queue < pair < int, int > > q;
                    q.push({i, j});

                    cc++;

                    while(!q.empty()) {
                        pair < int, int > val = q.front();
                        q.pop();

                        if(used[val.first][val.second] != 0) continue;
                        used[val.first][val.second] = cc;

                        for(int d = 0; d < dir.size(); d++) {
                            pair < int, int > to = { val.first + dir[d].first, val.second + dir[d].second };
                            
                            if(to.first < 0 || to.second < 0) continue;
                            if(to.first >= H || to.second >= W) continue;

                            if(dif(val, to) <= blendingConst) q.push(to);
                        }
                    }
                }
            }
        }

        for(int c = 1; c <= cc; c++) {
            int l = W, r = 0, u = H, d = 0;

            for(int i = 0; i < H; i++) {
                for(int j = 0; j < W; j++) {
                    if(used[i][j] == c) {
                        l = min(l, j);
                        r = max(r, j);
                        u = min(u, i);
                        d = max(d, i);
                        res--;
                    }
                }
            }
            res += (r - l + 1) * (d - u + 1);
        }

        if(res <= 150) return 4;
        else return 2;
    }
    else return 1;
}

• Subtask 1: 51.9118 / 100