Submission #296693

#	Time	Username	Problem	Language	Result	Execution time	Memory
296693		williamMBDK	Art Class (IOI13_artclass)	C++14	56 / 100	114 ms	18532 KiB

artclass

#include<bits/stdc++.h>
using namespace std;
#include "artclass.h"
#define int long long
// difference in size of components
int H, W, R[500][500], G[500][500], B[500][500];
vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int we(pair<int,int> p1, pair<int,int> p2){
	int dr = abs(R[p1.first][p1.second] - R[p2.first][p2.second]);
	int dg = abs(G[p1.first][p1.second] - G[p2.first][p2.second]);
	int db = abs(B[p1.first][p1.second] - B[p2.first][p2.second]);
	int diff = dr * dr + dg * dg + db * db;
	return diff;
}
int we2(pair<int,int> p1, pair<int,int> p2){
	int dr = abs(R[p1.first][p1.second] - R[p2.first][p2.second]);
	int dg = abs(G[p1.first][p1.second] - G[p2.first][p2.second]);
	int db = abs(B[p1.first][p1.second] - B[p2.first][p2.second]);
	int diff = dr + dg + db;
	return diff;
}
bool isedge(pair<int,int> p1, pair<int,int> p2){
	return we(p1,p2) < 10000;
}
signed style(signed _H, signed _W, signed _R[500][500], signed _G[500][500], signed _B[500][500]) {
    	H = _H;
    	W = _W;
    	int sc1 = 0, sc2 = 0, sc3 = 0, sc4 = 0;
    	for(int i = 0; i < H; i++){
    		for(int j = 0; j < W; j++){
    			R[i][j] = _R[i][j];
    			G[i][j] = _G[i][j];
    			B[i][j] = _B[i][j];
    			sc2 += (G[i][j] > 200);
    		}
    	}
    	vector<vector<bool>> v (H, vector<bool> (W));
    	int c = 0;
	vector<int> edges;
	int bigedges  = 0;
    	for(int i = 0; i < H; i++){
    		for(int j = 0; j < W; j++){
    			if(!v[i][j]){
    				int size = 0;
    				queue<pair<int,int>> q;
    				q.push({i,j});
    				while(!q.empty()){
    					auto curr = q.front(); q.pop();
    					if(v[curr.first][curr.second]) continue;
    					v[curr.first][curr.second] = 1;
    					size++;
    					for(auto dir : dirs){
    						int ni = curr.first + dir.first;
    						int nj = curr.second + dir.second;
    						if(ni >= 0 && ni < H && nj >= 0 && nj < W){
						       	if(isedge(curr, {ni,nj})) q.push({ni, nj});
							edges.push_back(we(curr, {ni,nj}));
							bigedges += we(curr,{ni,nj}) > 30000;
    						}
    					}
    				}
    				c += (size != 1);
    			}
    		}
    	}
	int sum = 0;
	for(int i = 0; i < edges.size(); i++) sum += edges[i];
	int sumdiff = 0;
	int avg = sum / edges.size();
	for(int i = 0; i < edges.size(); i++) sumdiff += abs(edges[i] - avg);
	/*cout << "sum: " << sum << endl;
	cout << "sumdiff: " << sumdiff << endl;
   	cout << "count: " << c << endl;
	cout << "bigedges: " << bigedges << endl;*/
	if(bigedges == 0) return 4;
	if(c >= 29 && sum >= 1500000000) return 3;
	if(c <= 4 && sumdiff < 50000000) return 4;
	if(bigedges > 1000 || c > 4) return 1;
	return 2;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:67:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < edges.size(); i++) sum += edges[i];
      |                 ~~^~~~~~~~~~~~~~
artclass.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < edges.size(); i++) sumdiff += abs(edges[i] - avg);
      |                 ~~^~~~~~~~~~~~~~
artclass.cpp:28:10: warning: unused variable 'sc1' [-Wunused-variable]
   28 |      int sc1 = 0, sc2 = 0, sc3 = 0, sc4 = 0;
      |          ^~~
artclass.cpp:28:28: warning: unused variable 'sc3' [-Wunused-variable]
   28 |      int sc1 = 0, sc2 = 0, sc3 = 0, sc4 = 0;
      |                            ^~~
artclass.cpp:28:37: warning: unused variable 'sc4' [-Wunused-variable]
   28 |      int sc1 = 0, sc2 = 0, sc3 = 0, sc4 = 0;
      |                                     ^~~

• Subtask 1: 56 / 100