oj.uz

답안 #816533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
816533 2023-08-09T05:32:23 Z Magikarp4000 미술 수업 (IOI13_artclass) C++17
32 / 100
 66 ms 11792 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 = 15;
const int LINEVAR = 50;
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] >= 30) num++;
    if (num >= 6 && line >= 7) return 1;
    int num1 = 0;
    FOR(i,0,vn) if (cnts[i] >= h*w/5) num1++;
    if (num1 >= num*3/5) return 4;
    // 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/15) 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 <= 15) return 4; 
        }
    }
    int gre = 0;
    FOR(i,0,h) FOR(j,0,w) gre += green(j,i);
    if (gre >= h*w*0.25) 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+0 && gre > blu+0) return 2;
    // FORX(u,cnts) if (u >= h*w/4) return 4;
    return 3;
}

Subtask #1
32.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 7168 KB Output isn't correct
2 Correct 41 ms 7824 KB Output is correct
3 Correct 51 ms 8376 KB Output is correct
4 Incorrect 49 ms 7488 KB Output isn't correct
5 Incorrect 53 ms 7708 KB Output isn't correct
6 Incorrect 49 ms 7372 KB Output isn't correct
7 Incorrect 54 ms 7644 KB Output isn't correct
8 Correct 15 ms 7212 KB Output is correct
9 Correct 31 ms 7156 KB Output is correct
10 Incorrect 28 ms 4384 KB Output isn't correct
11 Correct 38 ms 7080 KB Output is correct
12 Correct 66 ms 10448 KB Output is correct
13 Correct 52 ms 7108 KB Output is correct
14 Correct 52 ms 10300 KB Output is correct
15 Correct 51 ms 8180 KB Output is correct
16 Correct 40 ms 11580 KB Output is correct
17 Incorrect 64 ms 11556 KB Output isn't correct
18 Correct 43 ms 7152 KB Output is correct
19 Correct 55 ms 11540 KB Output is correct
20 Incorrect 51 ms 8228 KB Output isn't correct
21 Correct 32 ms 7120 KB Output is correct
22 Incorrect 41 ms 7248 KB Output isn't correct
23 Correct 40 ms 8892 KB Output is correct
24 Incorrect 44 ms 7116 KB Output isn't correct
25 Incorrect 47 ms 7840 KB Output isn't correct
26 Correct 53 ms 9588 KB Output is correct
27 Correct 36 ms 8420 KB Output is correct
28 Incorrect 41 ms 7212 KB Output isn't correct
29 Correct 56 ms 6236 KB Output is correct
30 Correct 51 ms 6652 KB Output is correct
31 Incorrect 66 ms 7176 KB Output isn't correct
32 Correct 42 ms 7188 KB Output is correct
33 Incorrect 61 ms 6968 KB Output isn't correct
34 Correct 42 ms 7168 KB Output is correct
35 Correct 40 ms 7104 KB Output is correct
36 Correct 41 ms 7172 KB Output is correct
37 Correct 48 ms 7288 KB Output is correct
38 Correct 44 ms 7812 KB Output is correct
39 Correct 47 ms 8380 KB Output is correct
40 Correct 25 ms 7196 KB Output is correct
41 Incorrect 47 ms 7204 KB Output isn't correct
42 Correct 29 ms 7204 KB Output is correct
43 Incorrect 41 ms 7172 KB Output isn't correct
44 Incorrect 50 ms 7632 KB Output isn't correct
45 Incorrect 45 ms 6348 KB Output isn't correct
46 Incorrect 54 ms 6220 KB Output isn't correct
47 Incorrect 51 ms 11580 KB Output isn't correct
48 Correct 34 ms 8320 KB Output is correct
49 Correct 30 ms 5028 KB Output is correct
50 Correct 39 ms 5728 KB Output is correct
51 Correct 39 ms 6844 KB Output is correct
52 Correct 53 ms 10768 KB Output is correct
53 Correct 48 ms 7180 KB Output is correct
54 Incorrect 51 ms 7376 KB Output isn't correct
55 Correct 49 ms 7196 KB Output is correct
56 Incorrect 30 ms 7212 KB Output isn't correct
57 Correct 50 ms 7240 KB Output is correct
58 Correct 45 ms 7872 KB Output is correct
59 Correct 47 ms 7200 KB Output is correct
60 Incorrect 49 ms 7116 KB Output isn't correct
61 Correct 45 ms 7120 KB Output is correct
62 Incorrect 44 ms 6316 KB Output isn't correct
63 Incorrect 49 ms 7308 KB Output isn't correct
64 Correct 44 ms 11576 KB Output is correct
65 Correct 35 ms 5168 KB Output is correct
66 Incorrect 18 ms 2892 KB Output isn't correct
67 Incorrect 32 ms 7140 KB Output isn't correct
68 Correct 45 ms 6088 KB Output is correct
69 Incorrect 26 ms 5412 KB Output isn't correct
70 Correct 27 ms 5372 KB Output is correct
71 Incorrect 48 ms 7064 KB Output isn't correct
72 Incorrect 33 ms 7216 KB Output isn't correct
73 Incorrect 66 ms 7116 KB Output isn't correct
74 Incorrect 50 ms 7516 KB Output isn't correct
75 Incorrect 43 ms 7492 KB Output isn't correct
76 Correct 39 ms 5764 KB Output is correct
77 Correct 51 ms 11452 KB Output is correct
78 Incorrect 43 ms 9340 KB Output isn't correct
79 Incorrect 58 ms 8384 KB Output isn't correct
80 Correct 46 ms 6980 KB Output is correct
81 Correct 45 ms 6904 KB Output is correct
82 Correct 41 ms 7552 KB Output is correct
83 Correct 50 ms 7088 KB Output is correct
84 Correct 49 ms 10476 KB Output is correct
85 Incorrect 53 ms 7732 KB Output isn't correct
86 Correct 35 ms 7120 KB Output is correct
87 Correct 46 ms 7620 KB Output is correct
88 Correct 38 ms 7188 KB Output is correct
89 Incorrect 48 ms 6384 KB Output isn't correct
90 Correct 40 ms 11616 KB Output is correct
91 Correct 53 ms 11792 KB Output is correct
92 Correct 49 ms 6356 KB Output is correct
93 Incorrect 35 ms 7156 KB Output isn't correct
94 Incorrect 52 ms 7436 KB Output isn't correct
95 Incorrect 54 ms 7548 KB Output isn't correct
96 Correct 47 ms 9608 KB Output is correct
97 Correct 39 ms 5604 KB Output is correct
98 Correct 39 ms 8528 KB Output is correct
99 Correct 41 ms 7180 KB Output is correct
100 Correct 42 ms 7168 KB Output is correct
101 Incorrect 34 ms 7112 KB Output isn't correct
102 Correct 45 ms 6732 KB Output is correct