Submission #280238

#	Time	Username	Problem	Language	Result	Execution time	Memory
280238		shayan_p	Art Class (IOI13_artclass)	C++14	73 / 100	122 ms	6392 KiB

artclass

// And you curse yourself for things you never done

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

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;

const int maxn = 510, mod = 1e9 + 7, inf = 1e9 + 10;

int n, m;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool mark[maxn][maxn];

void dfs(int x, int y, function<bool(int, int, int, int)> same){
    queue<pii> q;
    q.push({x, y});
    mark[x][y] = 1;
    while(sz(q)){
	x = q.front().F, y = q.front().S;
	q.pop();
	for(int i = 0; i < 4; i++){
	    int X = x + dx[i], Y = y + dy[i];
	    if(X >= 0 && Y >= 0 && X < n && Y < m && same(x, y, X, Y) && !mark[X][Y])
		mark[X][Y] = 1, q.push({X, Y});
	}
    }
}

int style(int n, int m, int R[500][500], int G[500][500], int B[500][500]) {
    ::n = n, ::m = m;
    
    ll sR = 0, sG = 0, sB = 0;
    ll green = 0;
    for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++)
	    sR+= R[i][j], sG+= G[i][j], sB+= B[i][j];
    double RR = double(sR) / n/m, GG = double(sG) / n/m, BB = double(sB) / n/m;
    auto calc_borders = [&](int eps, int cnt){
			    int borders = 0;
			    auto same = [&](int x, int y, int xx, int yy){
					    return (abs(R[x][y] - R[xx][yy]) <= eps) + (abs(G[x][y] - G[xx][yy]) <= eps) + (abs(B[x][y] - B[xx][yy]) <= eps) >= cnt;
					};    
			    for(int i = 0; i < n; i++)
				for(int j = 0; j < m-1; j++)
				    borders+= !same(i, j, i, j+1);
			    for(int i = 0; i < n-1; i++)
				for(int j = 0; j < m; j++)
				    borders+= !same(i, j, i+1, j);
			    return double(borders)/n/m;
			};
    auto calc_borders2 = [&](int eps, int cnt){
			    int borders = 0;
			    auto same = [&](int x, int y, int xx, int yy){
					    return (abs(R[x][y] - R[xx][yy]) <= eps) + (abs(G[x][y] - G[xx][yy]) <= eps) + (abs(B[x][y] - B[xx][yy]) <= eps) <= cnt;
					};    
			    for(int i = 0; i < n; i++)
				for(int j = 0; j < m-1; j++)
				    borders+= !same(i, j, i, j+1);
			    for(int i = 0; i < n-1; i++)
				for(int j = 0; j < m; j++)
				    borders+= !same(i, j, i+1, j);
			    return double(borders)/n/m;
			};
    auto same_dfs = [&](int x, int y, int xx, int yy){
			const int eps = 40, cnt = 3;
			return (abs(R[x][y] - R[xx][yy]) <= eps) + (abs(G[x][y] - G[xx][yy]) <= eps) + (abs(B[x][y] - B[xx][yy]) <= eps) >= cnt;
		    };
    int comp = 0;
    for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++)
	    if(!mark[i][j])
		comp++, dfs(i, j, same_dfs);
    //    cout << comp << endl;
    //    cout << calc_borders(60, 3) << endl;
    //    cout << RR << " " << GG << " " << BB << endl;
    if(calc_borders2(10, 2) <= 0.9)
	return 3;
    if(BB >= 100)
	return 1;
    if(comp <= 10)
	return 4;
    return 2;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:46:8: warning: unused variable 'green' [-Wunused-variable]
   46 |     ll green = 0;
      |        ^~~~~
artclass.cpp:50:12: warning: unused variable 'RR' [-Wunused-variable]
   50 |     double RR = double(sR) / n/m, GG = double(sG) / n/m, BB = double(sB) / n/m;
      |            ^~
artclass.cpp:50:35: warning: unused variable 'GG' [-Wunused-variable]
   50 |     double RR = double(sR) / n/m, GG = double(sG) / n/m, BB = double(sB) / n/m;
      |                                   ^~
artclass.cpp:51:10: warning: variable 'calc_borders' set but not used [-Wunused-but-set-variable]
   51 |     auto calc_borders = [&](int eps, int cnt){
      |          ^~~~~~~~~~~~

• Subtask 1: 73 / 100