Submission #59646

#	Time	Username	Problem	Language	Result	Execution time	Memory
59646		spencercompton	Art Class (IOI13_artclass)	C++17	38 / 100	1157 ms	19612 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
class Photo{
public:
	vector<double> vals;
	int id;
	Photo(double b, double c, double d, int a){
		id = a;
		vals.push_back(b);
		vals.push_back(c);
		vals.push_back(d);
	}
	double dif(Photo o){
		double ret = 0.0;
		for(int i = 0; i<vals.size(); i++){
			// cout << "# " << vals[i] << " " << o.vals[i] << endl;
			ret += (abs((vals[i]-o.vals[i]))/((vals[i]+o.vals[i])/2.0)) * (abs((vals[i]-o.vals[i]))/((vals[i]+o.vals[i])/2.0));
		}
		return ret;
	}
};
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;
	// cout << "bef.push_back(Photo(" << prop << ", " << prop2 << ", " << avg << ", ";
	vector<Photo> bef;
	bef.push_back(Photo(0.129701, 0.415215, 525.074, 1));
	bef.push_back(Photo(0.0340065, 0.107065, 380.158, 1));
	bef.push_back(Photo(0.144998, 0.305855, 492.401, 1));
	bef.push_back(Photo(0.506903, 0.659035, 452.135, 1));
	bef.push_back(Photo(0.483542, 0.819391, 606.021, 1));
	bef.push_back(Photo(0.243613, 0.337717, 581.979, 1));
	bef.push_back(Photo(0.138791, 0.430867, 533.324, 1));
	bef.push_back(Photo(0.426962, 0.755907, 488.104, 1));
	bef.push_back(Photo(0.546347, 0.9872, 476.483, 1));
	bef.push_back(Photo(0.339275, 0.542527, 333.051, 2));
	bef.push_back(Photo(0.410211, 0.436189, 294.282, 2));
	bef.push_back(Photo(0.256776, 0.378933, 255.156, 2));
	bef.push_back(Photo(0.238695, 0.322134, 222.552, 2));
	bef.push_back(Photo(0.0109204, 0.0240846, 205.803, 2));
	bef.push_back(Photo(0.420278, 0.475401, 287.292, 2));
	bef.push_back(Photo(0.300423, 0.39746, 306.677, 2));
	bef.push_back(Photo(0.146502, 0.308029, 259.855, 2));
	bef.push_back(Photo(0.614092, 0.666714, 222.093, 2));
	bef.push_back(Photo(0.905366, 0.90629, 396.251, 3));
	bef.push_back(Photo(0.118826, 0.217393, 342.139, 3));
	bef.push_back(Photo(0.806735, 0.810482, 416.098, 3));
	bef.push_back(Photo(0.539177, 0.58886, 342.484, 3));
	bef.push_back(Photo(0.00864615, 0.0278462, 302.699, 3));
	bef.push_back(Photo(0.791869, 0.795662, 574.879, 3));
	bef.push_back(Photo(0.113697, 0.237815, 310.981, 3));
	bef.push_back(Photo(0.880821, 0.883463, 331.845, 3));
	bef.push_back(Photo(0.907207, 0.911306, 367.308, 3));
	bef.push_back(Photo(0.546092, 0.984645, 330.526, 4));
	bef.push_back(Photo(0.869189, 0.870791, 133.619, 4));
	bef.push_back(Photo(0.443864, 0.872664, 237.789, 4));
	bef.push_back(Photo(0.842717, 0.85599, 485.569, 4));
	bef.push_back(Photo(0.97109, 0.974834, 271.879, 4));
	bef.push_back(Photo(0.542746, 0.965767, 339.007, 4));
	bef.push_back(Photo(0.615372, 0.792153, 144.815, 4));
	bef.push_back(Photo(0.925844, 0.992327, 362.619, 4));
	bef.push_back(Photo(0.994359, 0.995756, 422.932, 4));
	pair<double,int> best = make_pair(4242424242.0,-1);
	Photo now = Photo(prop,prop2,avg,-1);
	double tot[4] = {0,0,0,0};
	for(int i = 0; i<bef.size(); i++){
		pair<double,int> here = make_pair(bef[i].dif(now),i);
		// cout << "@ " << here.first << endl;
		tot[i/9] += here.first;
		best = min(best,here);
	}
	best = make_pair(tot[0],0);
	for(int i = 0; i<4; i++){
		best = min(best,make_pair(tot[i],i));
	}
	assert(best.second>=0);
	return best.second+1;
	// 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 member function 'double Photo::dif(Photo)':
artclass.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<vals.size(); i++){
                  ~^~~~~~~~~~~~
artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
artclass.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<q.size(); k++){
                   ~^~~~~~~~~
artclass.cpp:126:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int a = 0; a<dy.size(); a++){
                    ~^~~~~~~~~~
artclass.cpp:150:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i<=4 && i<=all.size(); i++){
                         ~^~~~~~~~~~~~
artclass.cpp:197:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<bef.size(); i++){
                 ~^~~~~~~~~~~
artclass.cpp:77:9: warning: unused variable 'rat' [-Wunused-variable]
  double rat = gsum/asum;
         ^~~

• Subtask 1: 38 / 100