Submission #59642

#	Time	Username	Problem	Language	Result	Execution time	Memory
59642		spencercompton	Art Class (IOI13_artclass)	C++17	25 / 100	1000 ms	39032 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
class Color{
public:
	double r, g, b;
	Color(){
		r = 0;
		g = 0;
		b = 0;
	}
	Color(int x, int y, int z){
		double tot = x+y+z;
		r = x;
		r/= tot;
		g = y;
		g/= tot;
		b = z;
		b /= tot;
	}
	bool operator<(const Color &o) const{
		if(r!=o.r){
			return r<o.r;
		}
		if(g!=o.g){
			return g<o.g;
		}
		return b<o.b;
	}
	bool cool(Color o, double tol){
		double val = (r-o.r)*(r-o.r) + (g-o.g) * (g-o.g) + (b-o.b) * (b-o.b);
		// cout << "@ " << val << " " << tol << endl;
		return val<=tol;
	}

};
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
	vector<Color> li;
	double gsum = 0.0;
	double asum = 0.0;
	// cout << "J " << endl;
	vector<Color> cc[H];
	double avg = 0.0;
	// cout << "G " << endl;
	for(int i = 0; i<H; i++){
		for(int j = 0; j<W; j++){
			avg += R[i][j] + G[i][j] + B[i][j];
			li.push_back(Color(R[i][j],G[i][j],B[i][j]));
			cc[i].push_back( Color(R[i][j],G[i][j],B[i][j]) );
			if(G[i][j] >=R[i][j] && G[i][j]>=B[i][j]){
				gsum++;
			}
			asum++;
		}
	}
	avg /= H*W;
	// cout << "F"  << endl;
	double rat = gsum/asum;
	// int tol = 5000;
	// double tol = 0.00003;
	double tol = 0.0005;
	int cnt = 0;
	sort(li.begin(),li.end());
	for(int i = 0; i<li.size(); i++){
		bool nex = true;
		for(int j = max(0,i-100); j<i && nex; j++){
			nex &= !li[i].cool(li[j],tol);
		}
		for(int j =0; nex && i>0 && j<100; j++){
			int ind = rand()%i;
			nex &= !li[i].cool(li[ind],tol);
		}
		if(nex){
			cnt++;
		}
	}
	// cout << cnt << " " << rat << endl;
	int cnt2 = 0;
	bool v[H][W];
	for(int i = 0; i<H; i++){
		for(int j = 0; j<W; j++){
			v[i][j] = false;
		}
	}
	vector<int> dx;
	vector<int> dy;
	for(int i = -2; i<=2; i++){
		for(int j = -2; j<=2; j++){
			if(abs(i)+abs(j)>=2){
				continue;
			}
			dy.push_back(i);
			dx.push_back(j);
		}
	}
	vector<int> all;
	for(int i = 0; i<H; i++){
		for(int j = 0; j<W; j++){
			if(v[i][j]){
				continue;
			}
			cnt2++;
			vector<pair<int, int> > q;
			v[i][j] = true;
			q.push_back(make_pair(i,j));
			for(int k = 0; k<q.size(); k++){
				for(int a = 0; a<dy.size(); a++){
					int ny = q[k].first + dy[a];
					int nx = q[k].second + dx[a];
					if(ny>=0 && ny<H && nx>=0 && nx<W && !v[ny][nx] && cc[q[k].first][q[k].second].cool(cc[ny][nx],tol)){
						v[ny][nx] = true;
						q.push_back(make_pair(ny,nx));
					}
				}
			}
			if(q.size()<=6){
				cnt2--;
				continue;
			}
			// cout <<
			all.push_back(q.size());
		}
	}
	sort(all.begin(),all.end());
	// for(int i = 0; i<all.size(); i++){
	// 	cout << all[i] << endl;
	// }
	// cout << "! " << cnt2 << endl;
	double prop = (double)all[all.size()-1] / (double)(H*W);
	double prop2 = 0.0;
	for(int i = 1; i<=4 && i<=all.size(); i++){
		prop2 += all[all.size()-i];
	}
	prop2 /= (double)(H*W);
	// cout << "Z"  << all[all.size()-1] << endl;
	// cout << prop << " " << prop2 << " " << avg << " " << rat << endl;
	vector<int> pos;

	if(prop2 >=0.1 && prop2<=0.85 && avg>=380.0 && avg <= 606.0){
		pos.push_back(1);
	}
	if(prop2 >=0.2 && prop2<=0.67 && avg>=205.0 && avg <= 310.0){
		pos.push_back(2);
	}
	if(prop2 >=0 && prop2<=0.91 && avg>=310.0 && avg <= 574.0){
		pos.push_back(3);
	}
	if(prop2 >=0.85 && prop2<=1.0 && avg>=133.0 && avg <= 485.0){
		pos.push_back(4);
	}
	if(pos.size()==0){
		assert(false);
	}
	else{
		return pos[rand()%(int)(pos.size())];
	}
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
artclass.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<q.size(); k++){
                   ~^~~~~~~~~
artclass.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int a = 0; a<dy.size(); a++){
                    ~^~~~~~~~~~
artclass.cpp:131:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i<=4 && i<=all.size(); i++){
                         ~^~~~~~~~~~~~
artclass.cpp:58:9: warning: unused variable 'rat' [-Wunused-variable]
  double rat = gsum/asum;
         ^~~
artclass.cpp:129:9: warning: unused variable 'prop' [-Wunused-variable]
  double prop = (double)all[all.size()-1] / (double)(H*W);
         ^~~~

• Subtask 1: 25 / 100