oj.uz

Submission #816002

# Submission time Handle Problem Language Result Execution time Memory
816002 2023-08-09T03:39:31 Z Magikarp4000 Art Class (IOI13_artclass) C++17
0 / 100
 5000 ms 11148 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 = 30;
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) {
    int diff = abs(r[y1][x1]-r[y2][x2])+abs(g[y1][x1]-g[y2][x2])+abs(b[y1][x1]-b[y2][x2]);
    return diff <= VAR;
}

void bfs(int sx, int sy, int idx) {
    queue<PII> q;
    q.push({sx,sy});
    while (!q.empty()) {
        int x = q.front().F, y = q.front().S;
        q.pop();
        z[y][x] = idx;
        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});
            }
        }
    }
    Coord cur = {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
    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);
    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 vn = v.size(), num = 0;
    FORX(u,v) {
        int val = (u.tp.S-u.le.S)*(u.ri.F-u.bt.F);
        int val1 = (u.ri.S-u.bt.S)*(u.tp.F-u.le.F);
        if (abs(val-val1) <= EPS) num++;
    }
    if (num >= 5) return 1;
    FOR(k,0,vn) {
        Coord u = v[k];
        if (abs(u.ri.F-u.tp.F) <= EPS1
            && abs(u.ri.S-u.bt.S) <= EPS1
            && abs(u.bt.F-u.le.F) <= EPS1
            && abs(u.tp.S-u.le.S) <= EPS1
        ) {
            int bad = 0;
            FOR(i,u.tp.S,u.bt.S+1) {
                FOR(j,u.le.F,u.ri.F+1) bad += z[i][j] != k+1;
            }
            if ((u.tp.S-u.bt.S)*(u.ri.F-u.le.F) <= h*w/10) continue;
            if (bad <= 5) return 4; 
        }
    }
    int gre = 0;
    FOR(i,0,h) FOR(j,0,w) gre += g[i][j];
    if (gre >= h*w*255/3) return 2;
    // FORX(u,cnts) if (u >= h*w/4) return 4;
    return 3;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 8628 KB Output isn't correct
2 Incorrect 39 ms 9296 KB Output isn't correct
3 Execution timed out 5039 ms 8052 KB Time limit exceeded
4 Incorrect 39 ms 8652 KB Output isn't correct
5 Correct 91 ms 8672 KB Output is correct
6 Execution timed out 5059 ms 6472 KB Time limit exceeded
7 Execution timed out 5048 ms 9228 KB Time limit exceeded
8 Correct 581 ms 9820 KB Output is correct
9 Execution timed out 5014 ms 5888 KB Time limit exceeded
10 Execution timed out 5075 ms 9020 KB Time limit exceeded
11 Incorrect 84 ms 9076 KB Output isn't correct
12 Incorrect 987 ms 9120 KB Output isn't correct
13 Execution timed out 5031 ms 8104 KB Time limit exceeded
14 Correct 104 ms 9916 KB Output is correct
15 Correct 151 ms 9968 KB Output is correct
16 Incorrect 2741 ms 8608 KB Output isn't correct
17 Execution timed out 5038 ms 5408 KB Time limit exceeded
18 Incorrect 1310 ms 9680 KB Output isn't correct
19 Correct 93 ms 8876 KB Output is correct
20 Execution timed out 5062 ms 9224 KB Time limit exceeded
21 Incorrect 34 ms 8960 KB Output isn't correct
22 Incorrect 71 ms 9320 KB Output isn't correct
23 Correct 310 ms 9884 KB Output is correct
24 Incorrect 1899 ms 8672 KB Output isn't correct
25 Execution timed out 5002 ms 9308 KB Time limit exceeded
26 Execution timed out 5060 ms 6312 KB Time limit exceeded
27 Incorrect 1730 ms 8740 KB Output isn't correct
28 Incorrect 98 ms 9476 KB Output isn't correct
29 Execution timed out 5065 ms 7944 KB Time limit exceeded
30 Incorrect 34 ms 8568 KB Output isn't correct
31 Execution timed out 5060 ms 9012 KB Time limit exceeded
32 Execution timed out 5045 ms 9376 KB Time limit exceeded
33 Incorrect 40 ms 7628 KB Output isn't correct
34 Correct 532 ms 5912 KB Output is correct
35 Incorrect 50 ms 10056 KB Output isn't correct
36 Execution timed out 5052 ms 7756 KB Time limit exceeded
37 Correct 325 ms 9344 KB Output is correct
38 Incorrect 2449 ms 8384 KB Output isn't correct
39 Incorrect 56 ms 9048 KB Output isn't correct
40 Incorrect 310 ms 9332 KB Output isn't correct
41 Execution timed out 5042 ms 7312 KB Time limit exceeded
42 Incorrect 1619 ms 10236 KB Output isn't correct
43 Execution timed out 5056 ms 8912 KB Time limit exceeded
44 Execution timed out 5073 ms 6280 KB Time limit exceeded
45 Incorrect 2097 ms 9808 KB Output isn't correct
46 Incorrect 3546 ms 6460 KB Output isn't correct
47 Incorrect 2758 ms 8836 KB Output isn't correct
48 Incorrect 47 ms 9420 KB Output isn't correct
49 Execution timed out 5074 ms 9692 KB Time limit exceeded
50 Correct 274 ms 9920 KB Output is correct
51 Execution timed out 5089 ms 6628 KB Time limit exceeded
52 Correct 291 ms 9400 KB Output is correct
53 Incorrect 956 ms 7900 KB Output isn't correct
54 Correct 167 ms 9472 KB Output is correct
55 Incorrect 69 ms 8912 KB Output isn't correct
56 Correct 72 ms 8744 KB Output is correct
57 Execution timed out 5052 ms 9552 KB Time limit exceeded
58 Execution timed out 5072 ms 9276 KB Time limit exceeded
59 Execution timed out 5086 ms 8456 KB Time limit exceeded
60 Incorrect 145 ms 9704 KB Output isn't correct
61 Execution timed out 5093 ms 8380 KB Time limit exceeded
62 Correct 331 ms 8780 KB Output is correct
63 Incorrect 38 ms 8908 KB Output isn't correct
64 Execution timed out 5079 ms 8952 KB Time limit exceeded
65 Execution timed out 5034 ms 9020 KB Time limit exceeded
66 Execution timed out 5056 ms 7456 KB Time limit exceeded
67 Execution timed out 5063 ms 8588 KB Time limit exceeded
68 Correct 278 ms 9748 KB Output is correct
69 Incorrect 31 ms 8364 KB Output isn't correct
70 Execution timed out 5071 ms 8892 KB Time limit exceeded
71 Execution timed out 5069 ms 7356 KB Time limit exceeded
72 Incorrect 210 ms 9404 KB Output isn't correct
73 Incorrect 117 ms 9148 KB Output isn't correct
74 Incorrect 3894 ms 10016 KB Output isn't correct
75 Correct 2677 ms 10336 KB Output is correct
76 Incorrect 1850 ms 9804 KB Output isn't correct
77 Execution timed out 5078 ms 9188 KB Time limit exceeded
78 Incorrect 14 ms 7636 KB Output isn't correct
79 Execution timed out 5045 ms 9540 KB Time limit exceeded
80 Execution timed out 5065 ms 8260 KB Time limit exceeded
81 Correct 799 ms 9892 KB Output is correct
82 Incorrect 117 ms 8928 KB Output isn't correct
83 Execution timed out 5056 ms 8060 KB Time limit exceeded
84 Execution timed out 5063 ms 8684 KB Time limit exceeded
85 Execution timed out 5080 ms 5892 KB Time limit exceeded
86 Execution timed out 5079 ms 6808 KB Time limit exceeded
87 Execution timed out 5068 ms 7516 KB Time limit exceeded
88 Incorrect 155 ms 9620 KB Output isn't correct
89 Execution timed out 5090 ms 7368 KB Time limit exceeded
90 Execution timed out 5055 ms 5916 KB Time limit exceeded
91 Correct 1330 ms 10332 KB Output is correct
92 Incorrect 45 ms 9172 KB Output isn't correct
93 Correct 3246 ms 11148 KB Output is correct
94 Execution timed out 5053 ms 8996 KB Time limit exceeded
95 Incorrect 55 ms 9620 KB Output isn't correct
96 Incorrect 3677 ms 9448 KB Output isn't correct
97 Incorrect 517 ms 10160 KB Output isn't correct
98 Incorrect 983 ms 6984 KB Output isn't correct
99 Incorrect 1542 ms 3268 KB Output isn't correct
100 Incorrect 49 ms 9164 KB Output isn't correct
101 Execution timed out 5072 ms 4932 KB Time limit exceeded
102 Execution timed out 5083 ms 10172 KB Time limit exceeded