제출 #1076121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076121		shmax	Art Class (IOI13_artclass)	C++17	98 / 100	91 ms	6364 KiB

artclass

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

using namespace std;

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

typedef struct {
    int r, g, b;
} RGB;

double ColourDistance(RGB e1, RGB e2) {
    long rmean = ((long) e1.r + (long) e2.r) / 2;
    long r = (long) e1.r - (long) e2.r;
    long g = (long) e1.g - (long) e2.g;
    long b = (long) e1.b - (long) e2.b;
    return sqrt((((512 + rmean) * r * r) >> 8) + 4 * g * g + (((767 - rmean) * b * b) >> 8));
}

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]));
            mtr[i][j] = tuple<int, int, int>(R[i][j], G[i][j], B[i][j]);
        }
    }

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

    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    auto calc = [&](int kd = 50, bool b = false) -> float {
        auto similar = [&](tuple<int, int, int> a, tuple<int, int, int> b) {
            int r1, g1, b1, r2, g2, b2;
            tie(r1, g1, b1) = a;
            tie(r2, g2, b2) = b;
            int t = ColourDistance({r1, g1, b1}, {r2, g2, b2});
            if (t < kd) return true;
            if (t > kd * 2) return false;
            return (rnd() % kd) > (t - kd);
//            return false;
//            return  < kd;
        };
        int cnt_min = 1e9;
        int cnt_max = 0;
        {
            for (int i = 0; i < N; i++) {
                int tc = 0;
                for (int j = 0; j < M - 1; j++) {
                    tc += !similar(mtr[i][j], mtr[i][j + 1]);
                }
                cnt_max += tc;
            }
        }
        return (float) cnt_max*1000 / (M*N);
    };
//
    if(calc(100) < 2) return 4;
    if(calc(50) > 250) return 3;
    if(calc(20) > 220) return 2;
    return 1;
//    cout<<calc(20)<<endl;

//    if(calc(50) > 390) return 3;
//    if(calc(10) > 600) return 2;
//    return 1;
//    if(calc(50) < 50) return 1;
//    if(calc(200) > 10) return 3;
//    return 2;
//    cout << calc(50) << endl;
//    if (calc(100) < 10) return 4;
//    if (calc(150) > 50) return 3;
//    return 2;
//    cout << calc(10) << endl;
//    cout << calc(100, true) << endl;

//    if (cnt < 1000) {
//        return 4;
//    }
//////
//    if (cnt > 8000) {
//        return 3;
//    }
//    cnt = 0;
//    kd = 200;
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < M - 1; j++) {
//            cnt += !similar(mtr[i][j], mtr[i][j + 1]);
//        }
//    }
//    cout << cnt<<endl;
//    return 1;
//    if (cnt < 20000) {
//        return 1;
//    }
//    return 2;

//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

//
//    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 (!similar(mtr[i][j], mtr[nx][ny])) 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 > 2200) return 3;
//    if (cnt < 380) return 4;
//    if (most_common < 111036) return 1;

//    return 2;
//    if (cnt < 3900) {
//        return 4;
//    }
//    if (cnt < 4200) {
//        if (rnd() % 2 == 0) return 1;
//        else return 4;
//    } else {
//        if (rnd() % 2 == 0) return 2;
//        else return 3;
//    }
//    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;

}

컴파일 시 표준 에러 (stderr) 메시지

artclass.cpp: In lambda function:
artclass.cpp:43:33: warning: comparison of integer expressions of different signedness: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |             return (rnd() % kd) > (t - kd);
      |                    ~~~~~~~~~~~~~^~~~~~~~~~
artclass.cpp: In lambda function:
artclass.cpp:47:13: warning: unused variable 'cnt_min' [-Wunused-variable]
   47 |         int cnt_min = 1e9;
      |             ^~~~~~~
artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:32:9: warning: unused variable 'most_common' [-Wunused-variable]
   32 |     int most_common = 0;
      |         ^~~~~~~~~~~

• Subtask 1: 98 / 100