oj.uz

Submission #816466

# Submission time Handle Problem Language Result Execution time Memory
816466 2023-08-09T05:12:05 Z Magikarp4000 Art Class (IOI13_artclass) C++17
10 / 100
 83 ms 12632 KB 
#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
const int VAR = 20;
const int LINEVAR = 60;
const int EPS = 10;
const int EPS1 = 10;

struct Coord {
    PII tp,ri,bt,le;
};

const int MAXN = 5e2+5;
int h, w, r[MAXN][MAXN], g[MAXN][MAXN], b[MAXN][MAXN], z[MAXN][MAXN];
vector<Coord> v;
vector<int> cnts;

bool same(int x1, int y1, int x2, int y2) {
    if (abs(r[y1][x1]-r[y2][x2]) > VAR) return 0;
    if (abs(g[y1][x1]-g[y2][x2]) > VAR) return 0;
    if (abs(b[y1][x1]-b[y2][x2]) > VAR) return 0;
    return 1;
    // int diff = abs(r[y1][x1]-r[y2][x2])+abs(g[y1][x1]-g[y2][x2])+abs(b[y1][x1]-b[y2][x2]);
}

bool black(int x, int y) {
    if (r[y][x] > LINEVAR) return 0;
    if (g[y][x] > LINEVAR) return 0;
    if (b[y][x] > LINEVAR) return 0;
    return 1;
}

bool green(int x, int y) {
    return (g[y][x] > r[y][x] && g[y][x] > b[y][x]);
}

void bfs(int sx, int sy, int idx) {
    queue<PII> q;
    q.push({sx,sy});
    Coord cur = {{INF,INF},{-INF,INF},{-INF,-INF},{INF,-INF}};
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front().F, y = q.front().S;
        q.pop();
        z[y][x] = idx;
        cnt++;
        if (y < cur.tp.S || (y == cur.tp.S && x < cur.tp.F)) cur.tp = {x,y};
        if (x > cur.ri.F || (x == cur.ri.F && y < cur.ri.S)) cur.ri = {x,y};
        if (y > cur.bt.S || (y == cur.bt.S && x > cur.bt.F)) cur.bt = {x,y};
        if (x < cur.le.F || (x == cur.le.F && y > cur.le.S)) cur.le = {x,y};
        FOR(i,0,4) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
            if (z[ny][nx]) continue;
            if (same(x,y,nx,ny)) {
                z[ny][nx] = idx;
                q.push({nx,ny});
            }
        }
    }
    // FOR(i,0,h) {
    //     FOR(j,0,w) {
    //         if (z[i][j]) {
    //             cur.tp = {j,i};
    //             break;
    //         }
    //     }
    // }
    // FORR(j,w-1,-1) {
    //     FOR(i,0,h) {
    //         if (z[i][j]) {
    //             cur.ri = {j,i};
    //             break;
    //         }
    //     }
    // }
    // FORR(i,h-1,-1) {
    //     FORR(j,w-1,-1) {
    //         if (z[i][j]) {
    //             cur.bt = {j,i};
    //             break;
    //         }
    //     }
    // }
    // FOR(j,0,w) {
    //     FORR(i,h,-1) {
    //         if (z[i][j]) {
    //             cur.le = {j,i};
    //             break;
    //         }
    //     }
    // }
    v.PB(cur);
    cnts.PB(cnt);
    // int cnt = 0;
    // FOR(i,0,h) FOR(j,0,w) cnt += z[i][j] > 0;
    // cnts.PB(cnt);
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    h = H, w = W;
    FOR(i,0,h) FOR(j,0,w) r[i][j] = R[i][j], g[i][j] = G[i][j], b[i][j] = B[i][j];
    int idx = 1;
    FOR(i,0,h) {
        FOR(j,0,w) {
            if (z[i][j]) continue;
            // if (r[i][j]+g[i][j]+b[i][j] <= VAR) continue;
            bfs(j,i,idx++);
        }
    }
    int line = 0;
    bool prev = 0;
    FOR(i,0,h) {
        int bad = 0;
        FOR(j,0,w) bad += !black(j,i);
        if (bad <= 15) {
            if (!prev) line++;
            prev = 1;
        }
        else prev = 0;
    }
    prev = 0;
    FOR(j,0,w) {
        int bad = 0;
        FOR(i,0,h) bad += !black(j,i);
        if (bad <= 15) {
            if (!prev) line++;
            prev = 1;
        }
        else prev = 0;
    }
    // cout << "line: " << line << ln;
    if (line >= 10) return 1;
    int vn = v.size(), num = 0;
    FOR(i,0,vn) {
        if (cnts[i] <= 20) continue;
        Coord u = v[i];
        // cout << u.tp.F << " " << u.tp.S << " ";
        // cout << u.ri.F << " " << u.ri.S << " ";
        // cout << u.bt.F << " " << u.bt.S << " ";
        // cout << u.le.F << " " << u.le.S << ln;
        // cout << cnts[i] << ln;
        int val = (u.le.S-u.tp.S)*(u.ri.F-u.bt.F);
        int val1 = (u.bt.S-u.ri.S)*(u.tp.F-u.le.F);
        if (abs(val-val1) <= EPS) num++;
    }
    // if (num >= 20) return 1;
    FOR(k,0,vn) {
        Coord u = v[k];
        int area = (u.bt.S-u.tp.S)*(u.ri.F-u.le.F);
        // cout << "area: " << area << ln;
        // if (area >= cnts[k]*9/10 && area <= cnts[k]*11/10) return 4;
        // continue;
        if (abs(u.ri.S-u.tp.S) <= EPS1
            && abs(u.ri.F-u.bt.F) <= EPS1
            && abs(u.bt.S-u.le.S) <= EPS1
            && abs(u.tp.F-u.le.F) <= EPS1
        ) {
            if (area <= h*w/10) continue;
            int bad = 0;
            FOR(i,u.tp.S,u.bt.S+1) {
                FOR(j,u.le.F,u.ri.F+1) {
                    if (z[i][j] != k+1) {
                        bad++;
                    }
                }
            }
            if (bad <= 10) return 4; 
        }
    }
    // int gre = 0;
    // FOR(i,0,h) FOR(j,0,w) gre += green(j,i);
    // if (gre >= h*w/3) return 2;
    int red = 0, gre = 0, blu = 0;
    FOR(i,0,h) FOR(j,0,w) red += r[i][j], gre += g[i][j], blu += b[i][j];
    if (gre > red && gre > blu) return 2;
    // FORX(u,cnts) if (u >= h*w/4) return 4;
    return 3;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10308 KB Output is correct
2 Correct 57 ms 10316 KB Output is correct
3 Correct 36 ms 6208 KB Output is correct
4 Correct 45 ms 8000 KB Output is correct
5 Correct 46 ms 7984 KB Output is correct
6 Incorrect 59 ms 7676 KB Output isn't correct
7 Correct 61 ms 9188 KB Output is correct
8 Correct 14 ms 2824 KB Output is correct
9 Correct 45 ms 7044 KB Output is correct
10 Correct 28 ms 6464 KB Output is correct
11 Correct 60 ms 7364 KB Output is correct
12 Correct 68 ms 9344 KB Output is correct
13 Correct 51 ms 10360 KB Output is correct
14 Correct 44 ms 8016 KB Output is correct
15 Incorrect 46 ms 8088 KB Output isn't correct
16 Correct 47 ms 8068 KB Output is correct
17 Incorrect 50 ms 7580 KB Output isn't correct
18 Correct 48 ms 10316 KB Output is correct
19 Correct 55 ms 10332 KB Output is correct
20 Incorrect 57 ms 8020 KB Output isn't correct
21 Incorrect 51 ms 7968 KB Output isn't correct
22 Incorrect 58 ms 8276 KB Output isn't correct
23 Correct 52 ms 7712 KB Output is correct
24 Correct 48 ms 7536 KB Output is correct
25 Correct 52 ms 8840 KB Output is correct
26 Incorrect 59 ms 8176 KB Output isn't correct
27 Incorrect 54 ms 8680 KB Output isn't correct
28 Incorrect 54 ms 8012 KB Output isn't correct
29 Incorrect 63 ms 7260 KB Output isn't correct
30 Incorrect 32 ms 8060 KB Output isn't correct
31 Correct 44 ms 8060 KB Output is correct
32 Correct 48 ms 7308 KB Output is correct
33 Incorrect 42 ms 8080 KB Output isn't correct
34 Incorrect 52 ms 8448 KB Output isn't correct
35 Correct 46 ms 6752 KB Output is correct
36 Correct 36 ms 8032 KB Output is correct
37 Correct 69 ms 8088 KB Output is correct
38 Incorrect 46 ms 7240 KB Output isn't correct
39 Correct 36 ms 9276 KB Output is correct
40 Incorrect 53 ms 8200 KB Output isn't correct
41 Incorrect 48 ms 8068 KB Output isn't correct
42 Correct 51 ms 12632 KB Output is correct
43 Correct 44 ms 6928 KB Output is correct
44 Incorrect 48 ms 8020 KB Output isn't correct
45 Correct 45 ms 5072 KB Output is correct
46 Incorrect 50 ms 6836 KB Output isn't correct
47 Incorrect 54 ms 8064 KB Output isn't correct
48 Correct 45 ms 8492 KB Output is correct
49 Incorrect 41 ms 7972 KB Output isn't correct
50 Incorrect 44 ms 8012 KB Output isn't correct
51 Incorrect 60 ms 6820 KB Output isn't correct
52 Incorrect 40 ms 5320 KB Output isn't correct
53 Correct 47 ms 6624 KB Output is correct
54 Correct 15 ms 7672 KB Output is correct
55 Incorrect 40 ms 8300 KB Output isn't correct
56 Incorrect 52 ms 8060 KB Output isn't correct
57 Incorrect 43 ms 8004 KB Output isn't correct
58 Correct 60 ms 10432 KB Output is correct
59 Incorrect 55 ms 8064 KB Output isn't correct
60 Correct 52 ms 10244 KB Output is correct
61 Incorrect 65 ms 9196 KB Output isn't correct
62 Incorrect 66 ms 8092 KB Output isn't correct
63 Incorrect 54 ms 8032 KB Output isn't correct
64 Correct 53 ms 7968 KB Output is correct
65 Incorrect 49 ms 8220 KB Output isn't correct
66 Incorrect 77 ms 8008 KB Output isn't correct
67 Incorrect 56 ms 7992 KB Output isn't correct
68 Incorrect 83 ms 8164 KB Output isn't correct
69 Correct 76 ms 10768 KB Output is correct
70 Incorrect 66 ms 8096 KB Output isn't correct
71 Correct 49 ms 7592 KB Output is correct
72 Correct 43 ms 7716 KB Output is correct
73 Correct 40 ms 9928 KB Output is correct
74 Incorrect 53 ms 8020 KB Output isn't correct
75 Incorrect 36 ms 8056 KB Output isn't correct
76 Incorrect 56 ms 8660 KB Output isn't correct
77 Correct 70 ms 10352 KB Output is correct
78 Correct 73 ms 8704 KB Output is correct
79 Incorrect 33 ms 8008 KB Output isn't correct
80 Incorrect 58 ms 7844 KB Output isn't correct
81 Incorrect 59 ms 8216 KB Output isn't correct
82 Correct 53 ms 8672 KB Output is correct
83 Incorrect 60 ms 7992 KB Output isn't correct
84 Incorrect 51 ms 7480 KB Output isn't correct
85 Incorrect 51 ms 8028 KB Output isn't correct
86 Incorrect 57 ms 8388 KB Output isn't correct
87 Incorrect 50 ms 7352 KB Output isn't correct
88 Correct 48 ms 8036 KB Output is correct
89 Incorrect 35 ms 5872 KB Output isn't correct
90 Correct 36 ms 6944 KB Output is correct
91 Incorrect 64 ms 8332 KB Output isn't correct
92 Incorrect 55 ms 7744 KB Output isn't correct
93 Correct 42 ms 6848 KB Output is correct
94 Correct 54 ms 7640 KB Output is correct
95 Correct 56 ms 8944 KB Output is correct
96 Incorrect 61 ms 7452 KB Output isn't correct
97 Correct 30 ms 6248 KB Output is correct
98 Correct 45 ms 6820 KB Output is correct
99 Correct 41 ms 6928 KB Output is correct
100 Correct 52 ms 8016 KB Output is correct
101 Incorrect 53 ms 8012 KB Output isn't correct
102 Correct 45 ms 12604 KB Output is correct