Submission #897474

#	Time	Username	Problem	Language	Result	Execution time	Memory
897474		Faisal_Saqib	Art Class (IOI13_artclass)	C++17	0 / 100	5057 ms	17888 KiB

artclass

#include "artclass.h"
/*
*/
#include <iostream>
#include <set>
#include <map>
#include <queue>
#define ll long long
using namespace std;
long long val(ll i,ll j,ll k)
{
	return (((i*256ll)+j)*256ll)+k;
}
int style(int n, int m, int R[500][500], int G[500][500], int B[500][500])
{
	int mx=-1*n*m;
	int mi=-mx;
	set<vector<int>> st;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			st.insert({R[i][j],G[i][j],B[i][j]});
			// run a bfs to find number of cell adjacent and equal
			queue<pair<int,int>> q;
			map<pair<int,int>,bool> vis;
			q.push({i,j});
			int sz=0;
			while(q.size())
			{
				auto f=q.front();
				sz++;
				q.pop();
				if((f.first>0) and R[f.first-1][f.second]==R[f.first][f.second] and G[f.first-1][f.second]==G[f.first][f.second] and B[f.first-1][f.second]==B[f.first][f.second] and !vis[{f.first-1,f.second}])
				{
					vis[{f.first-1,f.second}]=1;
					q.push({f.first-1,f.second});
				}
				if((f.second>0) and R[f.first][f.second-1]==R[f.first][f.second] and G[f.first][f.second-1]==G[f.first][f.second] and B[f.first][f.second-1]==B[f.first][f.second] and !vis[{f.first,f.second-1}])
				{
					vis[{f.first,f.second-1}]=1;
					q.push({f.first,f.second-1});
				}
				if((f.first<(n-1)) and R[f.first+1][f.second]==R[f.first][f.second] and G[f.first+1][f.second]==G[f.first][f.second] and B[f.first+1][f.second]==B[f.first][f.second] and !vis[{f.first+1,f.second}])
				{
					vis[{f.first+1,f.second}]=1;
					q.push({f.first+1,f.second});
				}
				if((f.second<(m-1)) and R[f.first][f.second+1]==R[f.first][f.second] and G[f.first][f.second+1]==G[f.first][f.second] and B[f.first][f.second+1]==B[f.first][f.second] and !vis[{f.first,f.second+1}])
				{
					vis[{f.first,f.second+1}]=1;
					q.push({f.first,f.second+1});
				}
			}
			mx=max(mx,sz);
			mi=min(mi,sz);
		}
	}
	if(mx<=(n+m+n+m))
	{
		// We check
		if(st.size()>=23)
			return 3;
		else
		{
			ll sum=0;
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)
				{
					sum+=val(R[i][j],G[i][j],B[i][j]);
				}
			}
			sum/=(n*m);
			if(sum>=(1e7))
			{
				return 4;
			}
			else
			{
				return 2;
			}
		}
	}
	else
	{
		return 1;
	}
}

• Subtask 1: 0 / 100