oj.uz

Submission #399092

# Submission time Handle Problem Language Result Execution time Memory
399092 2021-05-05T09:42:32 Z ACmachine Art Class (IOI13_artclass) C++17
78 / 100
 92 ms 12068 KB 
#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]);
    };
    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 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);
    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;
        }

    }


    return 2;
}

Compilation message

artclass.cpp: In lambda function:
artclass.cpp:81: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]
   81 |                 cnt += is_green({grid[i][j][0], grid[i][j][1], grid[i][j][2]});
      |                                                                              ^
artclass.cpp:81: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:81: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:163:12: warning: unused variable 'p' [-Wunused-variable]
  163 |     double p = get_green();
      |            ^

Subtask #1
78.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 10036 KB Output isn't correct
2 Correct 80 ms 10844 KB Output is correct
3 Incorrect 55 ms 8932 KB Output isn't correct
4 Incorrect 72 ms 10564 KB Output isn't correct
5 Correct 49 ms 9620 KB Output is correct
6 Correct 70 ms 10928 KB Output is correct
7 Correct 74 ms 10292 KB Output is correct
8 Correct 20 ms 4940 KB Output is correct
9 Correct 56 ms 10044 KB Output is correct
10 Correct 72 ms 10276 KB Output is correct
11 Incorrect 82 ms 12068 KB Output isn't correct
12 Correct 73 ms 10764 KB Output is correct
13 Correct 73 ms 11256 KB Output is correct
14 Correct 73 ms 10524 KB Output is correct
15 Correct 65 ms 10060 KB Output is correct
16 Incorrect 78 ms 11908 KB Output isn't correct
17 Correct 72 ms 10564 KB Output is correct
18 Correct 76 ms 11588 KB Output is correct
19 Correct 62 ms 9052 KB Output is correct
20 Correct 52 ms 9924 KB Output is correct
21 Correct 70 ms 11332 KB Output is correct
22 Correct 69 ms 9996 KB Output is correct
23 Correct 68 ms 9828 KB Output is correct
24 Incorrect 71 ms 10912 KB Output isn't correct
25 Correct 85 ms 11972 KB Output is correct
26 Incorrect 67 ms 10948 KB Output isn't correct
27 Correct 58 ms 8716 KB Output is correct
28 Correct 74 ms 10456 KB Output is correct
29 Correct 63 ms 9924 KB Output is correct
30 Correct 56 ms 9972 KB Output is correct
31 Correct 82 ms 11968 KB Output is correct
32 Incorrect 81 ms 11972 KB Output isn't correct
33 Correct 46 ms 7740 KB Output is correct
34 Incorrect 65 ms 10676 KB Output isn't correct
35 Correct 70 ms 9924 KB Output is correct
36 Correct 81 ms 12012 KB Output is correct
37 Correct 85 ms 11972 KB Output is correct
38 Correct 41 ms 7052 KB Output is correct
39 Correct 75 ms 11588 KB Output is correct
40 Correct 75 ms 11040 KB Output is correct
41 Correct 70 ms 11232 KB Output is correct
42 Correct 82 ms 11924 KB Output is correct
43 Correct 59 ms 8760 KB Output is correct
44 Correct 48 ms 7744 KB Output is correct
45 Correct 92 ms 11492 KB Output is correct
46 Correct 84 ms 12000 KB Output is correct
47 Correct 75 ms 10952 KB Output is correct
48 Incorrect 72 ms 10820 KB Output isn't correct
49 Correct 39 ms 6772 KB Output is correct
50 Correct 67 ms 10988 KB Output is correct
51 Correct 52 ms 9884 KB Output is correct
52 Correct 75 ms 11052 KB Output is correct
53 Correct 74 ms 10736 KB Output is correct
54 Correct 77 ms 10692 KB Output is correct
55 Correct 71 ms 11080 KB Output is correct
56 Correct 67 ms 10948 KB Output is correct
57 Incorrect 89 ms 11956 KB Output isn't correct
58 Correct 72 ms 11180 KB Output is correct
59 Incorrect 83 ms 11944 KB Output isn't correct
60 Incorrect 80 ms 11972 KB Output isn't correct
61 Correct 50 ms 7624 KB Output is correct
62 Correct 66 ms 10340 KB Output is correct
63 Correct 58 ms 8516 KB Output is correct
64 Correct 77 ms 11048 KB Output is correct
65 Incorrect 67 ms 11012 KB Output isn't correct
66 Correct 59 ms 10156 KB Output is correct
67 Correct 49 ms 7620 KB Output is correct
68 Incorrect 49 ms 7984 KB Output isn't correct
69 Correct 58 ms 9672 KB Output is correct
70 Correct 56 ms 9572 KB Output is correct
71 Correct 68 ms 10196 KB Output is correct
72 Correct 79 ms 11716 KB Output is correct
73 Correct 63 ms 10380 KB Output is correct
74 Correct 72 ms 10124 KB Output is correct
75 Correct 64 ms 10096 KB Output is correct
76 Correct 49 ms 9736 KB Output is correct
77 Incorrect 81 ms 11932 KB Output isn't correct
78 Correct 69 ms 9800 KB Output is correct
79 Correct 79 ms 11092 KB Output is correct
80 Correct 76 ms 11456 KB Output is correct
81 Correct 70 ms 10436 KB Output is correct
82 Correct 73 ms 10652 KB Output is correct
83 Correct 40 ms 8936 KB Output is correct
84 Correct 21 ms 7564 KB Output is correct
85 Correct 75 ms 9924 KB Output is correct
86 Correct 47 ms 9372 KB Output is correct
87 Correct 65 ms 10944 KB Output is correct
88 Incorrect 51 ms 9836 KB Output isn't correct
89 Correct 75 ms 10300 KB Output is correct
90 Correct 42 ms 6724 KB Output is correct
91 Correct 66 ms 10948 KB Output is correct
92 Incorrect 69 ms 9672 KB Output isn't correct
93 Correct 60 ms 10272 KB Output is correct
94 Incorrect 71 ms 10944 KB Output isn't correct
95 Correct 72 ms 10652 KB Output is correct
96 Correct 67 ms 10396 KB Output is correct
97 Correct 63 ms 10800 KB Output is correct
98 Correct 66 ms 9668 KB Output is correct
99 Incorrect 66 ms 10776 KB Output isn't correct
100 Correct 75 ms 10812 KB Output is correct
101 Correct 71 ms 11020 KB Output is correct
102 Correct 71 ms 10572 KB Output is correct