Submission #426566

#	Time	Username	Problem	Language	Result	Execution time	Memory
426566		Aldas25	Art Class (IOI13_artclass)	C++14	49 / 100	79 ms	5236 KiB

artclass

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;

int id (int i, int j) {
    return i * 510 + j;
}

int par[520*520], sz[520*520];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    par[b] = a;
    sz[a] += sz[b];
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {

    ll sumR = 0, sumG = 0, sumB = 0;
    FOR(i, 0, H-1) FOR(j, 0, W-1) {
        sumR += R[i][j];
        sumG += G[i][j];
        sumB += B[i][j];
        par[id(i,j)] = id(i,j);
        sz[id(i,j)] = 1;
    }

    //cout << " sumR = " << sumR << " sumG = " << sumG << " sumB = " << sumB << endl;
    ll area = ((ll)H)*((ll)W);
    ld avR = ((ld)sumR) / ((ld)area);
    ld avG = ((ld)sumG) / ((ld)area);
    ld avB = ((ld)sumB) / ((ld)area);
    //cout << fixed << setprecision(3) << " avR = " << avR << " avG = " << avG << " avB = " << avB << endl;

    ll maxD = 50;
    FOR(i, 0, H-1) FOR(j, 0, W-1) {
        if (i < H-1) {
            int d = 0;
            //d = abs(R[i][j] - R[i+1][j]) + abs(G[i][j] - G[i+1][j]) + abs(B[i][j] - B[i+1][j]);
            d = max(d, abs(R[i][j] - R[i+1][j]));
            d = max(d, abs(G[i][j] - G[i+1][j]));
            d = max(d, abs(B[i][j] - B[i+1][j]));
            if (d <= maxD)
                unite(id(i,j), id(i+1,j));
        }

        if (j < W-1) {
            int d = 0;
            d = max(d, abs(R[i][j] - R[i][j+1]));
            d = max(d, abs(G[i][j] - G[i][j+1]));
            d = max(d, abs(B[i][j] - B[i][j+1]));
            if (d <= maxD)
                unite(id(i,j), id(i,j+1));
        }
    }

    int conComponents = 0;
    FOR(i, 0, H-1) FOR(j, 0, W-1) {
        if (find(id(i,j)) != id(i,j)) continue;
        conComponents++;
    }

   // cout << " CC: " << conComponents << "\n";

    if (conComponents <= 3) return 4;
    else if (avB < min(avR, avG) - 25.0) return 2;
    else if (conComponents <= 10) return 4;
    else if (conComponents <= 500) return 1;
    else return 3;
    //cout << " ans = " << ans << endl;

    //return ans;
}

• Subtask 1: 49 / 100