#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 : (f / h > 25000 ? 2 : 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 : (f / h > 25000 ? 2 : 1);
| ~~~~~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
131 ms |
11948 KB |
Output is correct |
2 |
Correct |
107 ms |
11376 KB |
Output is correct |
3 |
Correct |
127 ms |
11816 KB |
Output is correct |
4 |
Correct |
119 ms |
11956 KB |
Output is correct |
5 |
Correct |
99 ms |
10736 KB |
Output is correct |
6 |
Correct |
113 ms |
11952 KB |
Output is correct |
7 |
Correct |
63 ms |
6124 KB |
Output is correct |
8 |
Correct |
102 ms |
11976 KB |
Output is correct |
9 |
Correct |
133 ms |
11988 KB |
Output is correct |
10 |
Correct |
131 ms |
11776 KB |
Output is correct |
11 |
Incorrect |
121 ms |
11956 KB |
Output isn't correct |
12 |
Correct |
114 ms |
11752 KB |
Output is correct |
13 |
Correct |
115 ms |
12044 KB |
Output is correct |
14 |
Correct |
98 ms |
10972 KB |
Output is correct |
15 |
Correct |
116 ms |
11960 KB |
Output is correct |
16 |
Correct |
123 ms |
11920 KB |
Output is correct |
17 |
Correct |
125 ms |
11996 KB |
Output is correct |
18 |
Incorrect |
111 ms |
11936 KB |
Output isn't correct |
19 |
Correct |
107 ms |
11948 KB |
Output is correct |
20 |
Correct |
119 ms |
12004 KB |
Output is correct |
21 |
Correct |
101 ms |
10844 KB |
Output is correct |
22 |
Incorrect |
117 ms |
12012 KB |
Output isn't correct |
23 |
Correct |
117 ms |
11976 KB |
Output is correct |
24 |
Correct |
99 ms |
11984 KB |
Output is correct |
25 |
Correct |
113 ms |
11480 KB |
Output is correct |
26 |
Correct |
112 ms |
11500 KB |
Output is correct |
27 |
Correct |
112 ms |
11964 KB |
Output is correct |
28 |
Correct |
109 ms |
11948 KB |
Output is correct |
29 |
Correct |
106 ms |
11332 KB |
Output is correct |
30 |
Correct |
57 ms |
6208 KB |
Output is correct |
31 |
Correct |
142 ms |
11984 KB |
Output is correct |
32 |
Correct |
111 ms |
11984 KB |
Output is correct |
33 |
Correct |
111 ms |
11248 KB |
Output is correct |
34 |
Incorrect |
97 ms |
11924 KB |
Output isn't correct |
35 |
Correct |
119 ms |
11976 KB |
Output is correct |
36 |
Correct |
105 ms |
11296 KB |
Output is correct |
37 |
Correct |
112 ms |
11488 KB |
Output is correct |
38 |
Correct |
108 ms |
11972 KB |
Output is correct |
39 |
Correct |
120 ms |
11988 KB |
Output is correct |
40 |
Correct |
62 ms |
7964 KB |
Output is correct |
41 |
Correct |
97 ms |
11924 KB |
Output is correct |
42 |
Incorrect |
111 ms |
11616 KB |
Output isn't correct |
43 |
Correct |
64 ms |
6396 KB |
Output is correct |
44 |
Correct |
113 ms |
11512 KB |
Output is correct |
45 |
Incorrect |
112 ms |
11224 KB |
Output isn't correct |
46 |
Correct |
113 ms |
11972 KB |
Output is correct |
47 |
Incorrect |
125 ms |
11920 KB |
Output isn't correct |
48 |
Incorrect |
102 ms |
11996 KB |
Output isn't correct |
49 |
Correct |
55 ms |
6092 KB |
Output is correct |
50 |
Correct |
106 ms |
11984 KB |
Output is correct |
51 |
Incorrect |
114 ms |
11976 KB |
Output isn't correct |
52 |
Correct |
104 ms |
10804 KB |
Output is correct |
53 |
Correct |
105 ms |
11192 KB |
Output is correct |
54 |
Correct |
110 ms |
11988 KB |
Output is correct |
55 |
Correct |
111 ms |
11552 KB |
Output is correct |
56 |
Correct |
118 ms |
11552 KB |
Output is correct |
57 |
Correct |
114 ms |
11964 KB |
Output is correct |
58 |
Correct |
116 ms |
11576 KB |
Output is correct |
59 |
Correct |
60 ms |
6428 KB |
Output is correct |
60 |
Correct |
116 ms |
11860 KB |
Output is correct |
61 |
Correct |
121 ms |
11472 KB |
Output is correct |
62 |
Incorrect |
119 ms |
11976 KB |
Output isn't correct |
63 |
Correct |
107 ms |
11156 KB |
Output is correct |
64 |
Incorrect |
100 ms |
11944 KB |
Output isn't correct |
65 |
Incorrect |
59 ms |
6440 KB |
Output isn't correct |
66 |
Correct |
126 ms |
12056 KB |
Output is correct |
67 |
Correct |
118 ms |
11992 KB |
Output is correct |
68 |
Correct |
113 ms |
11376 KB |
Output is correct |
69 |
Incorrect |
128 ms |
11668 KB |
Output isn't correct |
70 |
Correct |
117 ms |
12056 KB |
Output is correct |
71 |
Correct |
122 ms |
11904 KB |
Output is correct |
72 |
Incorrect |
106 ms |
12108 KB |
Output isn't correct |
73 |
Correct |
114 ms |
11928 KB |
Output is correct |
74 |
Correct |
106 ms |
11760 KB |
Output is correct |
75 |
Correct |
112 ms |
11200 KB |
Output is correct |
76 |
Incorrect |
117 ms |
11520 KB |
Output isn't correct |
77 |
Correct |
100 ms |
10936 KB |
Output is correct |
78 |
Incorrect |
27 ms |
3440 KB |
Output isn't correct |
79 |
Correct |
119 ms |
11956 KB |
Output is correct |
80 |
Correct |
118 ms |
11492 KB |
Output is correct |
81 |
Correct |
108 ms |
11064 KB |
Output is correct |
82 |
Correct |
106 ms |
11292 KB |
Output is correct |
83 |
Correct |
105 ms |
12076 KB |
Output is correct |
84 |
Incorrect |
123 ms |
11924 KB |
Output isn't correct |
85 |
Correct |
106 ms |
11956 KB |
Output is correct |
86 |
Correct |
105 ms |
11208 KB |
Output is correct |
87 |
Correct |
93 ms |
10552 KB |
Output is correct |
88 |
Correct |
97 ms |
11720 KB |
Output is correct |
89 |
Incorrect |
107 ms |
11972 KB |
Output isn't correct |
90 |
Correct |
110 ms |
11136 KB |
Output is correct |
91 |
Correct |
30 ms |
5780 KB |
Output is correct |
92 |
Correct |
117 ms |
11540 KB |
Output is correct |
93 |
Correct |
106 ms |
11008 KB |
Output is correct |
94 |
Incorrect |
112 ms |
11976 KB |
Output isn't correct |
95 |
Incorrect |
118 ms |
11916 KB |
Output isn't correct |
96 |
Correct |
119 ms |
11992 KB |
Output is correct |
97 |
Incorrect |
108 ms |
11416 KB |
Output isn't correct |
98 |
Correct |
112 ms |
11840 KB |
Output is correct |
99 |
Correct |
123 ms |
11952 KB |
Output is correct |
100 |
Correct |
111 ms |
11404 KB |
Output is correct |
101 |
Correct |
108 ms |
11936 KB |
Output is correct |
102 |
Correct |
115 ms |
11968 KB |
Output is correct |