#include <bits/stdc++.h>
#include "artclass.h"
using namespace std;
constexpr double DThreshold = 200;
constexpr size_t FRatio = 2;
vector<vector<int64_t>> sobel = vector<vector<int64_t>>({vector<int64_t>({-1, 0, 1}),
vector<int64_t>({-2, 0, 2}),
vector<int64_t>({-1, 0, 1})});
void bit_reverse(vector<complex<double>> &y, size_t lgn)
{
vector<bool> swapped(y.size(), 0);
for (size_t i = 0; i < y.size(); i++)
{
if (swapped[i])
continue;
size_t j = 0;
for (size_t k = 0; k < lgn; k++)
j |= ((i & (1 << k)) >> k) << (lgn - k - 1);
swap(y[i], y[j]);
swapped[i] = swapped[j] = 1;
}
}
void fft(vector<complex<double>> &y)
{
size_t const n = y.size(), lgn = __lg(n);
bit_reverse(y, lgn);
for (size_t s = 1; s <= lgn; s++)
{
size_t const m = 1 << s;
complex<double> const omega_m = polar(1.0, 2 * M_PI / m);
for (size_t i = 0; i < n; i += m)
{
complex<double> omega = 1.0;
for (size_t k = i; k < i + m / 2; k++)
{
complex<double> const u = y[k], v = omega * y[k + m / 2];
y[k] = u + v;
y[k + m / 2] = u - v;
omega *= omega_m;
}
}
}
}
template <typename T>
void rotate_c(vector<vector<T>> &y)
{
vector<vector<T>> z(y[0].size(), vector<T>(y.size()));
for (size_t i = 0; i < y.size(); i++)
for (size_t j = 0; j < y[0].size(); j++)
z[j][y.size() - i - 1] = y[i][j];
swap(y, z);
}
template <typename T>
size_t convolve(vector<vector<T>> const &y, vector<vector<T>> const &kernel)
{
size_t counter = 0;
for (size_t i = kernel.size() / 2; i < y.size() - kernel.size() / 2; i++)
for (size_t j = kernel[0].size() / 2; j < y[i].size() - kernel[0].size() / 2; j++)
{
T val = 0;
for (size_t k = 0; k < kernel.size(); k++)
for (size_t h = 0; h < kernel[k].size(); h++)
val += y[i - kernel.size() / 2 + k][j - kernel.size() / 2 + h] * kernel[k][h];
if (abs(val) > DThreshold)
counter++;
}
return counter;
}
size_t get_high_deriv(int H, int W, int arr[500][500])
{
vector<vector<int64_t>> image(H, vector<int64_t>(W));
for (size_t i = 0; i < H; i++)
for (size_t j = 0; j < W; j++)
image[i][j] = arr[i][j];
size_t ans = convolve(image, sobel);
rotate_c(sobel);
ans += convolve(image, sobel);
rotate_c(sobel);
rotate_c(sobel);
rotate_c(sobel);
return ans;
}
double get_high_freq(int H, int W, int arr[500][500])
{
size_t n1 = 1 << (32 - __builtin_clz(H)), n2 = 1 << (32 - __builtin_clz(W));
vector<vector<complex<double>>> y(n1, vector<complex<double>>(n2));
for (size_t i = 0; i < H; i++)
for (size_t j = 0; j < W; j++)
y[i][j] = arr[i][j];
for (size_t i = 0; i < n1; i++)
fft(y[i]);
rotate_c(y);
for (size_t i = 0; i < n2; i++)
fft(y[i]);
double ans = 0.0;
for (size_t i = n2 - n2 / FRatio; i < n2; i++)
for (size_t j = n1 - n1 / FRatio; j < n1; j++)
ans += abs(y[i][j]);
return ans;
}
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
double h = (double)(get_high_deriv(H, W, R) + get_high_deriv(H, W, G) +
get_high_deriv(H, W, B)) /
(double)(H * W);
double f = (get_high_freq(H, W, R) + get_high_freq(H, W, G) + get_high_freq(H, W, B)) / (H * W);
cout << "h : " << h << ", "
<< "f : " << f << '\n';
if (h < 0.15)
{
if (h < 0.06)
return f < 2200 ? 4 : 1;
return (f < 2500 || h < 0.01) ? 4 : 2;
}
return (f > 10000 || f > 8000 && h > 0.7) ? 3 : 1;
}
Compilation message
artclass.cpp: In function 'size_t get_high_deriv(int, int, int (*)[500])':
artclass.cpp:79:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
79 | for (size_t i = 0; i < H; i++)
| ~~^~~
artclass.cpp:80:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | for (size_t j = 0; j < W; j++)
| ~~^~~
artclass.cpp: In function 'double get_high_freq(int, int, int (*)[500])':
artclass.cpp:95:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | for (size_t i = 0; i < H; i++)
| ~~^~~
artclass.cpp:96:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
96 | for (size_t j = 0; j < W; j++)
| ~~^~~
artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:127:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
127 | return (f > 10000 || f > 8000 && h > 0.7) ? 3 : 1;
| ~~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
130 ms |
14184 KB |
Output isn't correct |
2 |
Incorrect |
141 ms |
14124 KB |
Output isn't correct |
3 |
Incorrect |
116 ms |
13572 KB |
Output isn't correct |
4 |
Incorrect |
108 ms |
13408 KB |
Output isn't correct |
5 |
Incorrect |
107 ms |
13228 KB |
Output isn't correct |
6 |
Incorrect |
154 ms |
13228 KB |
Output isn't correct |
7 |
Incorrect |
141 ms |
14376 KB |
Output isn't correct |
8 |
Incorrect |
139 ms |
14180 KB |
Output isn't correct |
9 |
Incorrect |
128 ms |
13612 KB |
Output isn't correct |
10 |
Incorrect |
134 ms |
13300 KB |
Output isn't correct |
11 |
Incorrect |
29 ms |
3448 KB |
Output isn't correct |
12 |
Incorrect |
122 ms |
13596 KB |
Output isn't correct |
13 |
Incorrect |
112 ms |
13168 KB |
Output isn't correct |
14 |
Incorrect |
115 ms |
12052 KB |
Output isn't correct |
15 |
Incorrect |
117 ms |
12996 KB |
Output isn't correct |
16 |
Incorrect |
102 ms |
12892 KB |
Output isn't correct |
17 |
Incorrect |
33 ms |
5880 KB |
Output isn't correct |
18 |
Incorrect |
113 ms |
13416 KB |
Output isn't correct |
19 |
Incorrect |
129 ms |
13428 KB |
Output isn't correct |
20 |
Incorrect |
126 ms |
13364 KB |
Output isn't correct |
21 |
Incorrect |
122 ms |
13544 KB |
Output isn't correct |
22 |
Incorrect |
116 ms |
12716 KB |
Output isn't correct |
23 |
Incorrect |
143 ms |
13608 KB |
Output isn't correct |
24 |
Incorrect |
134 ms |
13700 KB |
Output isn't correct |
25 |
Incorrect |
109 ms |
12872 KB |
Output isn't correct |
26 |
Incorrect |
116 ms |
13700 KB |
Output isn't correct |
27 |
Incorrect |
112 ms |
13412 KB |
Output isn't correct |
28 |
Incorrect |
115 ms |
12660 KB |
Output isn't correct |
29 |
Incorrect |
130 ms |
13152 KB |
Output isn't correct |
30 |
Incorrect |
102 ms |
13092 KB |
Output isn't correct |
31 |
Incorrect |
123 ms |
13280 KB |
Output isn't correct |
32 |
Incorrect |
136 ms |
13112 KB |
Output isn't correct |
33 |
Incorrect |
127 ms |
13584 KB |
Output isn't correct |
34 |
Incorrect |
111 ms |
13052 KB |
Output isn't correct |
35 |
Incorrect |
106 ms |
13020 KB |
Output isn't correct |
36 |
Incorrect |
125 ms |
13724 KB |
Output isn't correct |
37 |
Incorrect |
128 ms |
12996 KB |
Output isn't correct |
38 |
Incorrect |
60 ms |
6764 KB |
Output isn't correct |
39 |
Incorrect |
126 ms |
14160 KB |
Output isn't correct |
40 |
Incorrect |
111 ms |
12692 KB |
Output isn't correct |
41 |
Incorrect |
136 ms |
13140 KB |
Output isn't correct |
42 |
Incorrect |
125 ms |
13616 KB |
Output isn't correct |
43 |
Incorrect |
125 ms |
13468 KB |
Output isn't correct |
44 |
Incorrect |
135 ms |
14248 KB |
Output isn't correct |
45 |
Incorrect |
132 ms |
11276 KB |
Output isn't correct |
46 |
Incorrect |
165 ms |
14236 KB |
Output isn't correct |
47 |
Incorrect |
71 ms |
7228 KB |
Output isn't correct |
48 |
Incorrect |
118 ms |
12616 KB |
Output isn't correct |
49 |
Incorrect |
131 ms |
12876 KB |
Output isn't correct |
50 |
Incorrect |
63 ms |
8520 KB |
Output isn't correct |
51 |
Incorrect |
125 ms |
13988 KB |
Output isn't correct |
52 |
Incorrect |
109 ms |
12596 KB |
Output isn't correct |
53 |
Incorrect |
102 ms |
12000 KB |
Output isn't correct |
54 |
Incorrect |
119 ms |
13432 KB |
Output isn't correct |
55 |
Incorrect |
116 ms |
13196 KB |
Output isn't correct |
56 |
Incorrect |
125 ms |
12836 KB |
Output isn't correct |
57 |
Incorrect |
101 ms |
11624 KB |
Output isn't correct |
58 |
Incorrect |
79 ms |
7264 KB |
Output isn't correct |
59 |
Incorrect |
106 ms |
11864 KB |
Output isn't correct |
60 |
Incorrect |
118 ms |
12976 KB |
Output isn't correct |
61 |
Incorrect |
118 ms |
13584 KB |
Output isn't correct |
62 |
Incorrect |
119 ms |
12948 KB |
Output isn't correct |
63 |
Incorrect |
121 ms |
13424 KB |
Output isn't correct |
64 |
Incorrect |
65 ms |
7272 KB |
Output isn't correct |
65 |
Incorrect |
155 ms |
13968 KB |
Output isn't correct |
66 |
Incorrect |
110 ms |
12604 KB |
Output isn't correct |
67 |
Incorrect |
114 ms |
12664 KB |
Output isn't correct |
68 |
Incorrect |
120 ms |
12612 KB |
Output isn't correct |
69 |
Incorrect |
137 ms |
13800 KB |
Output isn't correct |
70 |
Incorrect |
64 ms |
6636 KB |
Output isn't correct |
71 |
Incorrect |
132 ms |
14268 KB |
Output isn't correct |
72 |
Incorrect |
117 ms |
12836 KB |
Output isn't correct |
73 |
Incorrect |
112 ms |
12664 KB |
Output isn't correct |
74 |
Incorrect |
131 ms |
13468 KB |
Output isn't correct |
75 |
Incorrect |
146 ms |
13956 KB |
Output isn't correct |
76 |
Incorrect |
128 ms |
14148 KB |
Output isn't correct |
77 |
Incorrect |
115 ms |
13108 KB |
Output isn't correct |
78 |
Incorrect |
118 ms |
13720 KB |
Output isn't correct |
79 |
Incorrect |
141 ms |
13972 KB |
Output isn't correct |
80 |
Incorrect |
131 ms |
13548 KB |
Output isn't correct |
81 |
Incorrect |
115 ms |
12940 KB |
Output isn't correct |
82 |
Incorrect |
102 ms |
13064 KB |
Output isn't correct |
83 |
Incorrect |
133 ms |
14128 KB |
Output isn't correct |
84 |
Incorrect |
138 ms |
14172 KB |
Output isn't correct |
85 |
Incorrect |
108 ms |
12304 KB |
Output isn't correct |
86 |
Incorrect |
135 ms |
12016 KB |
Output isn't correct |
87 |
Incorrect |
111 ms |
13372 KB |
Output isn't correct |
88 |
Incorrect |
126 ms |
13476 KB |
Output isn't correct |
89 |
Incorrect |
141 ms |
13520 KB |
Output isn't correct |
90 |
Incorrect |
79 ms |
6600 KB |
Output isn't correct |
91 |
Incorrect |
127 ms |
13568 KB |
Output isn't correct |
92 |
Incorrect |
117 ms |
13640 KB |
Output isn't correct |
93 |
Incorrect |
131 ms |
13744 KB |
Output isn't correct |
94 |
Incorrect |
129 ms |
12640 KB |
Output isn't correct |
95 |
Incorrect |
120 ms |
12508 KB |
Output isn't correct |
96 |
Incorrect |
127 ms |
14048 KB |
Output isn't correct |
97 |
Incorrect |
129 ms |
13232 KB |
Output isn't correct |
98 |
Incorrect |
134 ms |
13940 KB |
Output isn't correct |
99 |
Incorrect |
118 ms |
13628 KB |
Output isn't correct |
100 |
Incorrect |
115 ms |
12540 KB |
Output isn't correct |
101 |
Incorrect |
108 ms |
12940 KB |
Output isn't correct |
102 |
Incorrect |
104 ms |
12940 KB |
Output isn't correct |