oj.uz

Submission #837173

# Submission time Handle Problem Language Result Execution time Memory
837173 2023-08-25T06:52:47 Z unnick The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 0 ms 212 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct {
    int d;
    short x;
    short y;
} edge_t;

/*
**  **
..**..**
**  **
..**..**
*/

int main() {
    int w,h;
    cin >> h >> w;
    vector<edge_t> edges;
    {
        vector<int> alts(w*h);
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                cin >> alts[x+y*w];
            }
        }
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w-1; x++) {
                edges.push_back({.d = abs(alts[x+y*w]-alts[x+1+y*w]), .x = (short) (x*2+1), .y = (short) (y*2)});
            }
        }
        for (int y = 0; y < h-1; y++) {
            for (int x = 0; x < w; x++) {
                edges.push_back({.d = abs(alts[x+y*w]-alts[x+(y+1)*w]), .x = (short) (x*2), .y = (short) (y*2+1)});
            }
        }
        sort(edges.begin(), edges.end(), [](edge_t a, edge_t b){
            return a.d > b.d;
        });
    }
    int i;
    for (i = 0; i < edges.size(); i++) {
        edge_t ei = edges[i];
        bool valid = true;
        int clx = ei.x & ~1;
        int cly = ei.y & ~1;
        int chx = (ei.x+1) & ~1;
        int chy = (ei.y+1) & ~1;
        for (int j = 0; j < i; j++) {
            edge_t ej = edges[j];
            if (ej.x <= clx && ej.y <= cly || ej.x >= chx && ej.y >= chy) {
                valid = false;
                break;
            }
        }
        if (!valid) break;
    }
    int i1 = i;
    for (i = 0; i < edges.size(); i++) {
        edge_t ei = edges[i];
        bool valid = true;
        int clx = ei.x & ~1;
        int cly = (ei.y+1) & ~1;
        int chx = (ei.x+1) & ~1;
        int chy = ei.y & ~1;
        for (int j = 0; j < i; j++) {
            edge_t ej = edges[j];
            if (ej.x <= clx && ej.y >= cly || ej.x >= chx && ej.y <= chy) {
                valid = false;
                break;
            }
        }
        if (!valid) break;
    }
    int i2 = i;
    i = max(i1, i2);
    // for (auto edge : edges) {
    //     cout << edge.x << "," << edge.y << "|" << edge.d << " ";
    // }
    // cout << "\n";
    // cout << i1 << " " << i2 << "\n";
    cout << edges[i].d << "\n";
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
joioi.cpp:55:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |             if (ej.x <= clx && ej.y <= cly || ej.x >= chx && ej.y >= chy) {
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~
joioi.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
joioi.cpp:72:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |             if (ej.x <= clx && ej.y >= cly || ej.x >= chx && ej.y <= chy) {
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -