Submission #837173

#	Time	Username	Problem	Language	Result	Execution time	Memory
837173		unnick	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	0 ms	212 KiB

joioi

#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 (stderr)

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
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40