Submission #679869

#	Time	Username	Problem	Language	Result	Execution time	Memory
679869		bashkort	Art Class (IOI13_artclass)	C++17	43 / 100	2800 ms	6264 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>

using namespace std;

int n, m, R[500][500], G[500][500], B[500][500];

int dist(int i, int j, int x, int y) {
    return abs(R[i][j] - R[x][y]) + abs(B[i][j] - B[x][y]) + abs(G[i][j] - G[x][y]);
}

bool black(int i, int j) {
    return R[i][j] + B[i][j] + G[i][j] <= 20;
}

int same(int i, int j, int x, int y) {
    return dist(i, j, x, y) <= 150;
}

bool is_rectangle(int i, int j, int x, int y) {
    int cnt = 0;

    for (int a = i; a <= x; ++a) {
        for (int b = j; b <= y; ++b) {
            if (same(a, b, i, j)) {
                cnt += 1;
            }
        }
    }

    if (double(cnt) / ((x - i + 1) * (y - j + 1)) >= 0.999) {
        return true;
    } else {
        return false;
    }
}

int color_number() {
    vector<pair<int, int>> cols;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            bool any = false;

            for (auto [x, y] : cols) {
                if (same(i, j, x, y)) {
                    any = true;
                    break;
                }
            }

            if (!any) {
                cols.emplace_back(i, j);
            }
        }
    }

    return cols.size();
}

int black_number() {
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (black(i, j)) {
                ans += 1;
            }
        }
    }

    return ans;
}

int check1() {

}

int check2() {

}

int check3() {

}

int check4() {

}

bool any_rectangles() {
    const int rect_size = min({50, n / 2, m / 2});

    for (int i = rect_size - 1; i < n; ++i) {
        for (int j = rect_size - 1; j < m; ++j) {
            if (is_rectangle(i - rect_size + 1, j - rect_size + 1, i, j)) {
                return true;
            }
        }
    }

    return false;
}


bool any_big_rectangles() {
    const int rect_size = min({70, n / 2, m / 2});

    for (int i = rect_size - 1; i < n; ++i) {
        for (int j = rect_size - 1; j < m; ++j) {
            if (is_rectangle(i - rect_size + 1, j - rect_size + 1, i, j)) {
                return true;
            }
        }
    }

    return false;
}

int count_diff() {
    int ans = 0;

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            ans += !same(i - 1, j, i, j);
            ans += !same(i, j - 1, i, j);
        }
    }

    return ans;
}

int style(int n, int m, int R[500][500], int G[500][500], int B[500][500]) {
    memcpy(::R, R, sizeof(::R)), memcpy(::G, G, sizeof(::G)), memcpy(::B, B, sizeof(::B));
    ::n = n, ::m = m;

    int color_cnt = color_number();
    int black_cnt = black_number();

    cerr << color_cnt << " " << black_cnt << endl;

    bool any_big = any_big_rectangles();
    bool any_rect = any_rectangles();
    int diff = count_diff();

    cerr << "any big: " << any_big << endl;
    cerr << "any rect: " << any_rect << endl;
    cerr << "diff: " << diff << endl;
    cerr << n * m << endl;

    if (color_cnt < 100 && color_cnt >= 3 && black_cnt > 50 && !any_rect && diff >= n * m / 3) {
        return 3;
    }
    if (color_cnt < 15 && black_cnt > 50 && any_rect) {
        return 1;
    }
    if (color_cnt < 10 && any_big) {
        return 4;
    }

    return 2;
}

Compilation message (stderr)

artclass.cpp: In function 'int check1()':
artclass.cpp:77:1: warning: no return statement in function returning non-void [-Wreturn-type]
   77 | }
      | ^
artclass.cpp: In function 'int check2()':
artclass.cpp:81:1: warning: no return statement in function returning non-void [-Wreturn-type]
   81 | }
      | ^
artclass.cpp: In function 'int check3()':
artclass.cpp:85:1: warning: no return statement in function returning non-void [-Wreturn-type]
   85 | }
      | ^
artclass.cpp: In function 'int check4()':
artclass.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
   89 | }
      | ^

• Subtask 1: 43 / 100