제출 #1359968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359968		pcheloveks	미술 수업 (IOI13_artclass)	C++20	41 / 100	32 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 {
        int contr = 0;

        for(int i = 0; i < H - 1; i++) {
            for(int j = 0; j < W - 1; j++) {
                if(dif({i, j}, {i + 1, j}) >= 200) contr++;
                if(dif({i, j}, {i, j + 1}) >= 200) contr++;
            }
        }

        if(contr >= 1000) return 1;

        blendingConst = 50;
        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);
                        }
                    }
                }
            }
        }
        if(cc <= 20) return 4;
        else return 2;
    }
}

• 서브태스크 1: 40.8824 / 100