Submission #170808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
170808	2019-12-26T11:57:39 Z	AlexLuchianov	Art Class (IOI13_artclass)	C++14	100 / 100	311 ms	14256 KB

artclass

#include "artclass.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <set>
#include <cmath>

using ll = long long;
using ld = long double;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

bool isgreen(int red, int green, int blue){
  return red + 20 <= green && blue + 20 <= green ;
}

bool isred(int red, int green, int blue){
  return 150 <= red && 50 <= green && 50 <= blue;
}
bool isblue(int red, int green, int blue){
  return 50 <= red && 50 <= green && 150 <= blue;
}

int const whitethreshold = 530;

bool iswhite(int red, int green, int blue){
  return whitethreshold <= red + green + blue;
}

int const nmax = 500;
int black[1 + nmax][1 + nmax];
int up[1 + nmax];

int red[1 + nmax][1 + nmax];
int green[1 + nmax][1 + nmax];
int blue[1 + nmax][1 + nmax];

int dif(int x, int y, int x2, int y2){
  return fabs(red[x][y] - red[x2][y2]) +
         fabs(green[x][y] - green[x2][y2]) +
         fabs(blue[x][y] - blue[x2][y2]);
}

int biggestrectangle(int n, int m){
  int result = 0;
  for(int j = 0; j < m; j++)
    up[j] = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++){
      if(black[i][j] == 1 && (i == 0 || dif(i, j, i - 1, j) <= 50))
        up[j]++;
      else
        up[j] = 0;
    }
    for(int j = 0; j < m; j++) {
      int smin = up[j];
      for(int j2 = j; j2 < m; j2++) {
        smin = MIN(smin, up[j2]);
        result = MAX(result, smin * (j2 - j + 1));
      }
    }
  }
  return result;
}

int white[1 + nmax][1 + nmax];

int biggestrectanglewhite(int n, int m){
  int result = 0;
  for(int j = 0; j < m; j++)
    up[j] = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++){
      if(white[i][j] == 1 && (i == 0 || dif(i, j, i - 1, j) <= 50))
        up[j]++;
      else
        up[j] = 0;
    }
    for(int j = 0; j < m; j++) {
      int smin = up[j];
      for(int j2 = j; j2 < m; j2++) {
        smin = MIN(smin, up[j2]);
        result = MAX(result, smin * (j2 - j + 1));
      }
    }
  }
  return result;
}

std::set<int> used;

bool cross(int x, int y, int sz, int n, int m){
  if(0 <= x - sz && x + sz <= n && 0 <= y - sz && y + sz <= m) {

    for(int y2 = y - sz; y2 <= y + sz; y2++)
      if(20 < dif(x, y, x, y2))
        return 0;
    for(int x2 = x - sz; x2 <= x + sz; x2++)
      if(20 < dif(x, y, x2, y))
        return 0;
    return 20 < dif(x, y, x + sz, y + sz) &&
           20 < dif(x, y, x + sz, y - sz) &&
           20 < dif(x, y, x - sz, y + sz) &&
           20 < dif(x, y, x - sz, y - sz)
    ;
  } else
    return 0;
}

int value[1 + nmax][1 + nmax];

int style(int n, int m, int R[nmax][nmax], int G[nmax][nmax], int B[nmax][nmax]) {
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      red[i][j] = R[i][j];
      green[i][j] = G[i][j];
      blue[i][j] = B[i][j];
    }

  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      value[i][j] = (red[i][j] * 0.3 + green[i][j] * 0.59 + blue[i][j] * 0.11);
  int result = 0;

  for(int i = 0;i < n; i++)
    for(int j = 0; j < m - 1; j++)
      result += fabs(value[i][j] - value[i][j + 1]);

  for(int i = 0; i < n - 1; i++)
    for(int j = 0; j < m; j++)
      result += fabs(value[i][j] - value[i + 1][j]);

  std::ofstream out ("artclass.txt");
  ld totalgreen = 0, totaltotal = 0;
  //out << n << " " << m << '\n';

  used.clear();

  int crosses = 0;

  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      crosses += cross(i, j, 20, n, m);

  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      black[i][j] = (0 == iswhite(R[i][j], G[i][j], B[i][j]));
      white[i][j] = iswhite(R[i][j], G[i][j], B[i][j]);
      used.insert((R[i][j]<<16) |
                  (G[i][j]<<8)  |
                  (B[i][j])       );
    }
  /*
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++)
      if(isgreen(R[i][j], G[i][j], B[i][j]) == 1)
        out << " ";
      else
        out << "#";
    out << '\n';
  }
  */

  //*
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      totalgreen += isgreen(R[i][j], G[i][j], B[i][j]);
    }
  //*/

  /*
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++)
      if(iswhite(R[i][j], G[i][j], B[i][j]))
        out << " ";
      else
        out << "#";
    out << '\n';
  }
  */

  ld blackpercent = ((double)biggestrectangle(n, m)) / (n * m);
  ld whitepercent = ((double)biggestrectanglewhite(n, m)) / (n * m);
  ld greenpercent = ((double)totalgreen) / (n * m);
  ld distribution = ((double)used.size()) / (n * m);
  ld variation = ((double)result) / (n * m);

  /*
  std::cerr << "Average variation " << ((double)result) / (n * m) << '\n';
  std::cerr << "Crosses:" << crosses << '\n';
  std::cerr << "Black rectangle: " << blackpercent << '\n';
  std::cerr << "Green: " << std::setprecision(6) << std::fixed << greenpercent << '\n';
  std::cerr << "White rectangle: " << whitepercent << '\n';
  std::cerr << "Distribution: " << distribution << '\n';
  //*/

  int points[5] = {0};
  /*
  points[2] = 1;

  if(2 <= crosses){
    points[1] += 10;
    points[4] += 10;
  }

  if(0.2 <= blackpercent)
    points[4] += 10;
  else if(0.1 <= blackpercent)
    points[4] += 7;

  if(0.1 <= whitepercent )
    points[1] += 5;
  else if(0.01 <= whitepercent)
    points[1] += 2;

  if(blackpercent <= 0.0009 && whitepercent <= 0.0009)
    points[3] += 8;
  else if(blackpercent <= 0.003 && whitepercent <= 0.003)
    points[3] += 6;


  if(0.1 <= greenpercent)
    points[2] += 7;
  else if(0.05 <= greenpercent)
    points[2] += 4;

  if(0.6 <= distribution)
    points[3] += 8;
  else if(0.3 <= distribution){
    points[2] += 4;
    points[3] += 4;
  }
  if(distribution <= 0.2) {
    points[2] -= 7;
    points[3] -= 7;
  }
  */

  if(variation <= 5)
    points[4] += 10;
  else if(variation <= 15)
    points[1] += 10;
  else if(variation <= 40)
    points[2] += 10;
  else
    points[3] += 10;
  int smax = 0;
  for(int i = 1;i <= 4; i++)
    smax = MAX(smax, points[i]);

  //std::cout << smax << '\n';

  for(int i = 1;i <= 4; i++)
    if(smax == points[i])
      return i;
  return 2;
}

Compilation message

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:134:22: warning: unused variable 'totaltotal' [-Wunused-variable]
   ld totalgreen = 0, totaltotal = 0;
                      ^~~~~~~~~~
artclass.cpp:182:6: warning: unused variable 'blackpercent' [-Wunused-variable]
   ld blackpercent = ((double)biggestrectangle(n, m)) / (n * m);
      ^~~~~~~~~~~~
artclass.cpp:183:6: warning: unused variable 'whitepercent' [-Wunused-variable]
   ld whitepercent = ((double)biggestrectanglewhite(n, m)) / (n * m);
      ^~~~~~~~~~~~
artclass.cpp:184:6: warning: unused variable 'greenpercent' [-Wunused-variable]
   ld greenpercent = ((double)totalgreen) / (n * m);
      ^~~~~~~~~~~~
artclass.cpp:185:6: warning: unused variable 'distribution' [-Wunused-variable]
   ld distribution = ((double)used.size()) / (n * m);
      ^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	230 ms	9848 KB	Output is correct
2	Correct	269 ms	12280 KB	Output is correct
3	Correct	241 ms	10020 KB	Output is correct
4	Correct	165 ms	7792 KB	Output is correct
5	Correct	269 ms	9756 KB	Output is correct
6	Correct	241 ms	13944 KB	Output is correct
7	Correct	129 ms	10460 KB	Output is correct
8	Correct	187 ms	12672 KB	Output is correct
9	Correct	185 ms	10020 KB	Output is correct
10	Correct	267 ms	11640 KB	Output is correct
11	Correct	221 ms	8440 KB	Output is correct
12	Correct	143 ms	10104 KB	Output is correct
13	Correct	246 ms	10016 KB	Output is correct
14	Correct	278 ms	12536 KB	Output is correct
15	Correct	264 ms	12216 KB	Output is correct
16	Correct	214 ms	9432 KB	Output is correct
17	Correct	164 ms	12664 KB	Output is correct
18	Correct	248 ms	10488 KB	Output is correct
19	Correct	203 ms	10584 KB	Output is correct
20	Correct	272 ms	11860 KB	Output is correct
21	Correct	224 ms	9912 KB	Output is correct
22	Correct	170 ms	12792 KB	Output is correct
23	Correct	284 ms	10664 KB	Output is correct
24	Correct	190 ms	9940 KB	Output is correct
25	Correct	228 ms	9464 KB	Output is correct
26	Correct	250 ms	9820 KB	Output is correct
27	Correct	227 ms	10032 KB	Output is correct
28	Correct	193 ms	10180 KB	Output is correct
29	Correct	242 ms	10468 KB	Output is correct
30	Correct	162 ms	6904 KB	Output is correct
31	Correct	245 ms	9308 KB	Output is correct
32	Correct	124 ms	10536 KB	Output is correct
33	Correct	38 ms	9336 KB	Output is correct
34	Correct	261 ms	10768 KB	Output is correct
35	Correct	181 ms	9720 KB	Output is correct
36	Correct	138 ms	9976 KB	Output is correct
37	Correct	205 ms	10084 KB	Output is correct
38	Correct	111 ms	9848 KB	Output is correct
39	Correct	274 ms	12280 KB	Output is correct
40	Correct	135 ms	7368 KB	Output is correct
41	Correct	257 ms	12248 KB	Output is correct
42	Correct	288 ms	11656 KB	Output is correct
43	Correct	244 ms	12524 KB	Output is correct
44	Incorrect	311 ms	12360 KB	Output isn't correct
45	Correct	255 ms	9916 KB	Output is correct
46	Correct	128 ms	6136 KB	Output is correct
47	Correct	177 ms	9276 KB	Output is correct
48	Incorrect	231 ms	8928 KB	Output isn't correct
49	Correct	145 ms	6008 KB	Output is correct
50	Correct	230 ms	9592 KB	Output is correct
51	Correct	200 ms	9080 KB	Output is correct
52	Correct	247 ms	12124 KB	Output is correct
53	Correct	95 ms	10424 KB	Output is correct
54	Correct	283 ms	12152 KB	Output is correct
55	Correct	198 ms	8212 KB	Output is correct
56	Correct	240 ms	13836 KB	Output is correct
57	Correct	203 ms	11132 KB	Output is correct
58	Correct	236 ms	13048 KB	Output is correct
59	Correct	281 ms	9804 KB	Output is correct
60	Correct	127 ms	9932 KB	Output is correct
61	Correct	198 ms	8896 KB	Output is correct
62	Correct	271 ms	10916 KB	Output is correct
63	Incorrect	245 ms	10996 KB	Output isn't correct
64	Correct	267 ms	11580 KB	Output is correct
65	Correct	212 ms	11160 KB	Output is correct
66	Incorrect	200 ms	11128 KB	Output isn't correct
67	Correct	140 ms	10616 KB	Output is correct
68	Correct	198 ms	10040 KB	Output is correct
69	Correct	223 ms	11620 KB	Output is correct
70	Correct	165 ms	7560 KB	Output is correct
71	Correct	257 ms	11128 KB	Output is correct
72	Correct	196 ms	7672 KB	Output is correct
73	Correct	275 ms	12024 KB	Output is correct
74	Correct	247 ms	11228 KB	Output is correct
75	Incorrect	157 ms	10616 KB	Output isn't correct
76	Incorrect	286 ms	11136 KB	Output isn't correct
77	Correct	255 ms	13888 KB	Output is correct
78	Correct	152 ms	10744 KB	Output is correct
79	Correct	292 ms	14200 KB	Output is correct
80	Correct	219 ms	10744 KB	Output is correct
81	Correct	239 ms	12396 KB	Output is correct
82	Correct	253 ms	11384 KB	Output is correct
83	Incorrect	206 ms	10872 KB	Output isn't correct
84	Correct	204 ms	10232 KB	Output is correct
85	Correct	204 ms	12764 KB	Output is correct
86	Correct	165 ms	9720 KB	Output is correct
87	Correct	256 ms	10296 KB	Output is correct
88	Correct	254 ms	10232 KB	Output is correct
89	Correct	252 ms	13720 KB	Output is correct
90	Incorrect	216 ms	9080 KB	Output isn't correct
91	Correct	152 ms	7544 KB	Output is correct
92	Correct	264 ms	11648 KB	Output is correct
93	Correct	63 ms	3360 KB	Output is correct
94	Correct	258 ms	14256 KB	Output is correct
95	Correct	197 ms	9464 KB	Output is correct
96	Correct	232 ms	9012 KB	Output is correct
97	Correct	260 ms	9936 KB	Output is correct
98	Correct	182 ms	9468 KB	Output is correct
99	Correct	204 ms	10488 KB	Output is correct
100	Correct	271 ms	12280 KB	Output is correct
101	Correct	193 ms	10488 KB	Output is correct
102	Correct	149 ms	10104 KB	Output is correct