Submission #418912

#	Time	Username	Problem	Language	Result	Execution time	Memory
418912		jacquesamsel	Rectangles (IOI19_rect)	C++14	15 / 100	5040 ms	28296 KiB

rect

#include <bits/stdc++.h>
using namespace std;

void print_vvint(vector<vector<int>>& grid) {
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

int max_col(vector<vector<int>>& grid, int x, int y1, int y2) {
    int m = INT32_MIN;
    for (int y = y1; y <= y2; y++) {
        m = max(m, grid[y][x]);
    }
    return m;
}

int max_row(vector<vector<int>>& grid, int y, int x1, int x2) {
    int m = INT32_MIN;
    for (int x = x1; x <= x2; x++) {
        m = max(m, grid[y][x]);
    }
    return m;
}

bool is_valid(vector<vector<int>>& grid, int x1, int y1, int x2, int y2) {
    int m = INT32_MIN;
    for (int y = y1; y <= y2; y++) {
        for (int x = x1; x <= x2; x++) {
            m = max(m, grid[y][x]);
        }
    }
    // top + bottom
    for (int x = x1; x <= x2; x++) {
        int maxCol = max_col(grid, x, y1, y2);
        if (maxCol >= grid[y1-1][x] || maxCol >= grid[y2+1][x]) return false;
    }
    // left + right
    for (int y = y1; y <= y2; y++) {
        int maxRow = max_row(grid, y, x1, x2);
        if (maxRow >= grid[y][x1-1] || maxRow >= grid[y][x2+1]) return false;
    }
    return true;
}

int64_t count_rectangles(std::vector<std::vector<int> > a) {
    int accumulator = 0;
    for (int y1 = 1; y1 < a.size()-1; y1++) {
		for (int x1 = 1; x1 < a[y1].size()-1; x1++) {
            for (int y2 = y1; y2 < a.size()-1; y2++) {
                for (int x2 = x1; x2 < a[y2].size()-1; x2++) {
                    // cout << "checking (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")" << endl;
                    // cout << is_valid(a, x1, y1, x2, y2) << endl;
                    if (is_valid(a, x1, y1, x2, y2)) {
                        // cout << "valid (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")" << endl;
                        accumulator++;
                    }
                }
            }
		}
	}
    return accumulator;
}

Compilation message (stderr)

rect.cpp: In function 'void print_vvint(std::vector<std::vector<int> >&)':
rect.cpp:5:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
rect.cpp:6:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |         for (int j = 0; j < grid[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
rect.cpp: In function 'int64_t count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int y1 = 1; y1 < a.size()-1; y1++) {
      |                      ~~~^~~~~~~~~~~~
rect.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int x1 = 1; x1 < a[y1].size()-1; x1++) {
      |                    ~~~^~~~~~~~~~~~~~~~
rect.cpp:53:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for (int y2 = y1; y2 < a.size()-1; y2++) {
      |                               ~~~^~~~~~~~~~~~
rect.cpp:54:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for (int x2 = x1; x2 < a[y2].size()-1; x2++) {
      |                                   ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28