Submission #1075867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075867		shmax	Art Class (IOI13_artclass)	C++17	0 / 100	75 ms	9212 KiB

artclass

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

using namespace std;

template<typename T>
using vec = vector<T>;


tuple<int, int, int> fix_color(int r, int g, int b) {
    return tuple<int, int, int>(r / 100, g / 100, b / 100);
}

int style(int N, int M, int R[500][500], int G[500][500], int B[500][500]) {
    map<tuple<int, int, int>, int> colors;
    vec<vec<tuple<int, int, int>>> mtr(N, vec<tuple<int, int, int>>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
//            colors.insert(fix_color(R[i][j], G[i][j], B[i][j]));
            colors[fix_color(R[i][j], G[i][j], B[i][j])]++;
            mtr[i][j] = fix_color(R[i][j], G[i][j], B[i][j]);
        }
    }

    vec<vec<bool>> used(N, vec<bool>(M, false));
    int cnt = 0;
    int most_common = 0;

    auto BFS = [&](int i, int j) {
        if (used[i][j]) return;
        cnt++;
        int sz = 1;
        queue<pair<int, int>> q;
        q.push({i, j});
        used[i][j] = true;
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            sz++;
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if (used[nx][ny]) continue;
                    if (mtr[nx][ny] != mtr[i][j]) continue;
                    used[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        most_common = max(most_common, sz);
    };
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < M; j++) {
//            BFS(i, j);
//        }
//    }
//    cout << most_common << " " << cnt << endl;
    if (cnt < 5000) {
        if (rand() % 2 == 0) return 0;
        else return 3;
    }else{
        if (rand() % 2 == 0) return 1;
        else return 2;
    }
//    set<int> s;
//    int n = 8;
//    mt19937 rnd(228);
//    map<tuple<int, int, int>, int> rnd_m;
//    for (int i = 0; i < N - n; i++) {
//        for (int j = 0; j < M - n; j++) {
//            set<tuple<int, int, int>> cur;
//            for (int k = 0; k < n; k++) {
//                for (int l = 0; l < n; l++) {
//                    cur.insert(mtr[i + k][j + l]);
//                }
//            }
//            int hash = 0;
//            for (auto &color: cur) {
//                if (rnd_m.find(color) == rnd_m.end()) {
//                    rnd_m[color] = rnd();
//                }
//                hash = hash * 228 + rnd_m[color];
//            }
//
//            s.insert(hash);
//        }
//    }
//
//    int most_common = 0;

//    cout << colors.
//
//            size()
//
//         << " " << most_common << " " << s.
//
//            size()
//
//         <<
//         endl;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:29:10: warning: variable 'BFS' set but not used [-Wunused-but-set-variable]
   29 |     auto BFS = [&](int i, int j) {
      |          ^~~

• Subtask 1: 0 / 100