#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};
void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;
template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
// make functions return [0..1]
int style(int h, int w, int R[500][500], int G[500][500], int B[500][500]) {
auto in_tolerance = [&](int a, int b){
return abs(a - b) < 15;
};
auto similar = [&](array<int, 3> a, array<int, 3> b){
return in_tolerance(a[0],b[0]) && in_tolerance(a[1], b[1]) && in_tolerance(a[2], b[2]);
};
auto similar3 = [&](array<int, 3> a, array<int, 3> b){
return abs(a[0] - b[0]) < 5 && abs(a[1] - b[1]) < 5 && abs(a[2] - b[2]) < 5;
};
vector<vector<array<int, 3>>> grid(500, vector<array<int,3>>(500));
REP(i, h){
REP(j, w){
grid[i][j] = {R[i][j], G[i][j], B[i][j]};
}
}
auto get_green = [&]()->double{
auto is_green = [&](array<double, 3> px)->double{ // high red and green?
double scaling = 1.0 * px[1] / 255.0;
REP(i, 3) px[i] *= scaling;
return max(0.0, 2 * px[1] - px[0] - px[2]);
};
double cnt = 0;
REP(i, h){
REP(j, w){
cnt += is_green({grid[i][j][0], grid[i][j][1], grid[i][j][2]});
}
}
return (double)cnt / (double)(h * w);
};
auto get_granularity = [&]()->double{
double res = 0;
REP(i, h){
REP(j, w){
double curr = 0;
REP(sm, 4){
if(dy[sm] < 0 || dx[sm] < 0) continue;
int ny = i + dy[sm];
int nx = j + dx[sm];
if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
if(!similar(grid[i][j], grid[ny][nx]))
curr+=1.0;
}
res += curr;
}
}
return res / (double)(h * w * 2);
};
auto get_sensitive_granularity = [&]()->double{
double res = 0;
REP(i, h){
REP(j, w){
double curr = 0;
REP(sm, 4){
if(dy[sm] < 0 || dx[sm] < 0) continue;
int ny = i + dy[sm];
int nx = j + dx[sm];
if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
if(!similar3(grid[i][j], grid[ny][nx]))
curr+=1.0;
}
res += curr;
}
}
return res / (double)(h * w * 2);
};
auto similar2 = [&](array<int, 3> a, array<int, 3> b){
int cutoff = 40;
return abs(a[0] - b[0]) < cutoff && abs(a[1] - b[1]) < cutoff && abs(a[2] - b[2]) < cutoff;
};
auto get_components = [&]()->array<double, 2>{ // also count disproportionate components
vector<vector<int>> visited(h, vector<int>(w, -1));
int curr_id = 0;
auto bfs = [&](int row, int col){
queue<array<int, 2>> q;
visited[row][col] = curr_id;
q.push({row, col});
while(!q.empty()){
auto v = q.front();
q.pop();
REP(sm, 4){
int ny = v[0] + dy[sm];
int nx = v[1] + dx[sm];
if(ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx] != -1 || !similar2(grid[ny][nx], grid[row][col]))
continue;
visited[ny][nx] = curr_id;
q.push({ny, nx});
}
}
};
vector<int> miny(h * w, INF);
vector<int> maxy(h * w, -INF);
vector<int> minx(h * w, INF);
vector<int> maxx(h * w, -INF);
vector<int> cnt(h * w, 0);
REP(i, h){
REP(j, w){
if(visited[i][j] == -1){
bfs(i, j);
curr_id++;
}
}
}
REP(i, h){
REP(j, w){
miny[visited[i][j]] = min(miny[visited[i][j]], i);
maxy[visited[i][j]] = max(maxy[visited[i][j]], i);
minx[visited[i][j]] = min(minx[visited[i][j]], j);
maxx[visited[i][j]] = max(maxx[visited[i][j]], j);
cnt[visited[i][j]]++;
}
}
int components = 0; // only 30+ px; ?
int disproportionate_components = 0;
REP(i, h * w){
if(cnt[i] > 10){
components++;
int s = abs(miny[i] - maxy[i]) * abs(minx[i] - maxx[i]);
double cut = 0.3;
if((double)cnt[i] / s < cut)
disproportionate_components++;
}
}
return {(1.0 * components) / (1.0 * h * w), 1.0 * disproportionate_components};
};
double p = get_green();
double p2 = get_granularity();
auto v3 = get_components();
//dbg(p, v3);
double p4 = get_sensitive_granularity();
/*
dbg(p4);
if(p2 > 0.25){
if(v3[0] > 0.01)
return 3;
else
return 2;
if(p2 > 0.5) return 3;
if(v3[1] < 10) return 2;
if(p < 5) return 3;
}else{
// 1 or 4
if(v3[0] < 0.001){
return 4;
}
else{
return 1;
}
}
*/
//dbg(p4)
if(v3[0] < 0.001) return 4;
if(p4 < 0.6) return 1;
if(v3[0] > 0.01 || v3[1] > 50) return 3;
return 2;
//else if(v3[0] < )
return 2;
}
Compilation message
artclass.cpp: In lambda function:
artclass.cpp:84:78: warning: narrowing conversion of '(&(&(& grid)->std::vector<std::vector<std::array<int, 3> > >::operator[](((std::vector<std::vector<std::array<int, 3> > >::size_type)i)))->std::vector<std::array<int, 3> >::operator[](((std::vector<std::array<int, 3> >::size_type)j)))->std::array<int, 3>::operator[](0)' from 'std::array<int, 3>::value_type' {aka 'int'} to 'double' [-Wnarrowing]
84 | cnt += is_green({grid[i][j][0], grid[i][j][1], grid[i][j][2]});
| ^
artclass.cpp:84:78: warning: narrowing conversion of '(&(&(& grid)->std::vector<std::vector<std::array<int, 3> > >::operator[](((std::vector<std::vector<std::array<int, 3> > >::size_type)i)))->std::vector<std::array<int, 3> >::operator[](((std::vector<std::array<int, 3> >::size_type)j)))->std::array<int, 3>::operator[](1)' from 'std::array<int, 3>::value_type' {aka 'int'} to 'double' [-Wnarrowing]
artclass.cpp:84:78: warning: narrowing conversion of '(&(&(& grid)->std::vector<std::vector<std::array<int, 3> > >::operator[](((std::vector<std::vector<std::array<int, 3> > >::size_type)i)))->std::vector<std::array<int, 3> >::operator[](((std::vector<std::array<int, 3> >::size_type)j)))->std::array<int, 3>::operator[](2)' from 'std::array<int, 3>::value_type' {aka 'int'} to 'double' [-Wnarrowing]
artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:184:12: warning: unused variable 'p' [-Wunused-variable]
184 | double p = get_green();
| ^
artclass.cpp:185:12: warning: unused variable 'p2' [-Wunused-variable]
185 | double p2 = get_granularity();
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
8520 KB |
Output is correct |
2 |
Correct |
78 ms |
11584 KB |
Output is correct |
3 |
Correct |
76 ms |
10520 KB |
Output is correct |
4 |
Correct |
63 ms |
10308 KB |
Output is correct |
5 |
Correct |
40 ms |
6728 KB |
Output is correct |
6 |
Correct |
41 ms |
7024 KB |
Output is correct |
7 |
Correct |
80 ms |
11104 KB |
Output is correct |
8 |
Correct |
72 ms |
10952 KB |
Output is correct |
9 |
Correct |
21 ms |
7500 KB |
Output is correct |
10 |
Correct |
84 ms |
10948 KB |
Output is correct |
11 |
Correct |
41 ms |
9028 KB |
Output is correct |
12 |
Incorrect |
89 ms |
11972 KB |
Output isn't correct |
13 |
Incorrect |
81 ms |
11896 KB |
Output isn't correct |
14 |
Correct |
50 ms |
9604 KB |
Output is correct |
15 |
Correct |
49 ms |
7620 KB |
Output is correct |
16 |
Correct |
73 ms |
11196 KB |
Output is correct |
17 |
Incorrect |
68 ms |
10788 KB |
Output isn't correct |
18 |
Correct |
77 ms |
10956 KB |
Output is correct |
19 |
Correct |
72 ms |
10820 KB |
Output is correct |
20 |
Correct |
66 ms |
10948 KB |
Output is correct |
21 |
Incorrect |
83 ms |
11884 KB |
Output isn't correct |
22 |
Correct |
58 ms |
10236 KB |
Output is correct |
23 |
Correct |
54 ms |
9880 KB |
Output is correct |
24 |
Correct |
67 ms |
10992 KB |
Output is correct |
25 |
Incorrect |
66 ms |
10056 KB |
Output isn't correct |
26 |
Correct |
83 ms |
11972 KB |
Output is correct |
27 |
Correct |
76 ms |
10756 KB |
Output is correct |
28 |
Correct |
62 ms |
9016 KB |
Output is correct |
29 |
Correct |
74 ms |
10620 KB |
Output is correct |
30 |
Correct |
56 ms |
10068 KB |
Output is correct |
31 |
Correct |
66 ms |
10656 KB |
Output is correct |
32 |
Correct |
69 ms |
11008 KB |
Output is correct |
33 |
Correct |
67 ms |
9832 KB |
Output is correct |
34 |
Correct |
78 ms |
11644 KB |
Output is correct |
35 |
Correct |
80 ms |
11460 KB |
Output is correct |
36 |
Correct |
58 ms |
8684 KB |
Output is correct |
37 |
Correct |
74 ms |
10332 KB |
Output is correct |
38 |
Correct |
67 ms |
9796 KB |
Output is correct |
39 |
Correct |
74 ms |
10696 KB |
Output is correct |
40 |
Correct |
71 ms |
10204 KB |
Output is correct |
41 |
Correct |
53 ms |
9924 KB |
Output is correct |
42 |
Incorrect |
88 ms |
12016 KB |
Output isn't correct |
43 |
Correct |
67 ms |
10932 KB |
Output is correct |
44 |
Correct |
68 ms |
9668 KB |
Output is correct |
45 |
Incorrect |
83 ms |
12084 KB |
Output isn't correct |
46 |
Correct |
66 ms |
10152 KB |
Output is correct |
47 |
Incorrect |
72 ms |
10904 KB |
Output isn't correct |
48 |
Correct |
58 ms |
8780 KB |
Output is correct |
49 |
Correct |
73 ms |
10932 KB |
Output is correct |
50 |
Correct |
47 ms |
7640 KB |
Output is correct |
51 |
Incorrect |
73 ms |
10836 KB |
Output isn't correct |
52 |
Correct |
47 ms |
7688 KB |
Output is correct |
53 |
Correct |
85 ms |
11844 KB |
Output is correct |
54 |
Correct |
49 ms |
7948 KB |
Output is correct |
55 |
Correct |
86 ms |
12052 KB |
Output is correct |
56 |
Correct |
83 ms |
12052 KB |
Output is correct |
57 |
Correct |
75 ms |
10556 KB |
Output is correct |
58 |
Correct |
72 ms |
11332 KB |
Output is correct |
59 |
Correct |
20 ms |
4940 KB |
Output is correct |
60 |
Correct |
84 ms |
11972 KB |
Output is correct |
61 |
Correct |
51 ms |
9736 KB |
Output is correct |
62 |
Correct |
60 ms |
10204 KB |
Output is correct |
63 |
Correct |
63 ms |
10176 KB |
Output is correct |
64 |
Correct |
73 ms |
11004 KB |
Output is correct |
65 |
Correct |
57 ms |
9668 KB |
Output is correct |
66 |
Correct |
75 ms |
11360 KB |
Output is correct |
67 |
Correct |
73 ms |
11076 KB |
Output is correct |
68 |
Correct |
85 ms |
11844 KB |
Output is correct |
69 |
Correct |
57 ms |
9688 KB |
Output is correct |
70 |
Incorrect |
75 ms |
10572 KB |
Output isn't correct |
71 |
Correct |
71 ms |
10480 KB |
Output is correct |
72 |
Correct |
61 ms |
10160 KB |
Output is correct |
73 |
Correct |
68 ms |
10176 KB |
Output is correct |
74 |
Correct |
72 ms |
10672 KB |
Output is correct |
75 |
Correct |
66 ms |
10304 KB |
Output is correct |
76 |
Correct |
100 ms |
11000 KB |
Output is correct |
77 |
Correct |
75 ms |
10696 KB |
Output is correct |
78 |
Incorrect |
47 ms |
8092 KB |
Output isn't correct |
79 |
Incorrect |
86 ms |
11972 KB |
Output isn't correct |
80 |
Correct |
72 ms |
10856 KB |
Output is correct |
81 |
Correct |
39 ms |
6736 KB |
Output is correct |
82 |
Correct |
83 ms |
11536 KB |
Output is correct |
83 |
Correct |
76 ms |
11036 KB |
Output is correct |
84 |
Correct |
66 ms |
9668 KB |
Output is correct |
85 |
Correct |
77 ms |
10692 KB |
Output is correct |
86 |
Correct |
70 ms |
10852 KB |
Output is correct |
87 |
Correct |
48 ms |
9260 KB |
Output is correct |
88 |
Correct |
73 ms |
10564 KB |
Output is correct |
89 |
Correct |
56 ms |
9916 KB |
Output is correct |
90 |
Correct |
71 ms |
10052 KB |
Output is correct |
91 |
Correct |
69 ms |
9940 KB |
Output is correct |
92 |
Correct |
71 ms |
10308 KB |
Output is correct |
93 |
Incorrect |
88 ms |
11972 KB |
Output isn't correct |
94 |
Correct |
68 ms |
9924 KB |
Output is correct |
95 |
Incorrect |
53 ms |
9824 KB |
Output isn't correct |
96 |
Correct |
69 ms |
11068 KB |
Output is correct |
97 |
Correct |
64 ms |
10908 KB |
Output is correct |
98 |
Correct |
57 ms |
8948 KB |
Output is correct |
99 |
Incorrect |
74 ms |
10948 KB |
Output isn't correct |
100 |
Correct |
70 ms |
9984 KB |
Output is correct |
101 |
Correct |
71 ms |
9796 KB |
Output is correct |
102 |
Incorrect |
85 ms |
11848 KB |
Output isn't correct |