Submission #667761

#	Time	Username	Problem	Language	Result	Execution time	Memory
667761		gavgav	Gardening (RMI21_gardening)	C++17	5 / 100	273 ms	524288 KiB

Main

#include <iostream>
#include <queue>
using namespace std;
struct rect{int left, top, rect_rows, rect_cols, rect_tar;};
int main(){
    int tests;
    scanf("%d", &tests);
    int rows, cols, target;
    while (tests){
        scanf("%d%d%d", &rows, &cols, &target);
        if (rows % 2 == 0 && cols % 2 == 0 && (rows / 2) * (cols / 2) >= target){
            short garden[rows][cols];
            queue <rect> rects;
            rects.push({0, 0, rows / 2, cols / 2, target});
            int title = 1;
            while (!rects.empty()){
                long long product = rects.front().rect_rows * rects.front().rect_cols;
                int sum = rects.front().rect_cols + rects.front().rect_rows, i = rects.front().top, j = rects.front().left;
                if (product == rects.front().rect_tar){
                    for (; i < rects.front().top + rects.front().rect_rows * 2; ++i){
                        for (j = rects.front().left; j < rects.front().left + rects.front().rect_cols * 2; ++j){
                            garden[i][j] = title + (i - rects.front().top) / 2 * rects.front().rect_cols + (j - rects.front().left) / 2;
                        }
                    }
                    --i;
                    title += (i - rects.front().top) / 2 * rects.front().rect_cols + (j - rects.front().left) / 2;
                }
                else if (rects.front().rect_cols == 1 || rects.front().rect_rows == 1){
                    break;
                }
                else if (sum - 2 >= product - rects.front().rect_tar && product - rects.front().rect_tar >= 2){
                    int x = 2, y;
                    for (; product - rects.front().rect_tar + 2 - x >= 2 && x <= rects.front().rect_cols && product - rects.front().rect_tar + 2 - x > rects.front().rect_rows; ++x);
                    y = product - rects.front().rect_tar + 2 - x;
                    for (; j < rects.front().left + x * 2; garden[i][j] = title, ++j);
                    --j;
                    for (; i < rects.front().top + y * 2; garden[i][j] = title, ++i);
                    --i;
                    for (; j >= rects.front().left; garden[i][j] = title, --j);
                    ++j;
                    for (; i >= rects.front().top; garden[i][j] = title, --i);
                    ++i;
                    ++title;
                    if (rects.front().rect_rows != y){
                        rects.push({rects.front().left, rects.front().top + y * 2, rects.front().rect_rows - y, x, (rects.front().rect_rows - y) * x});
                        if (rects.front().rect_cols != x){
                            rects.push({rects.front().left + x * 2, rects.front().top + y * 2, rects.front().rect_rows - y, rects.front().rect_cols - x, (rects.front().rect_rows - y) * (rects.front().rect_cols - x)});
                        }
                    }
                    if (rects.front().rect_cols != x) {
                        rects.push({rects.front().left + x * 2, rects.front().top, y,
                                    rects.front().rect_cols - x, y * (rects.front().rect_cols - x)});
                    }
                    rects.push({i + 1, j + 1, y - 1, x - 1, (x - 1) * (y - 1)});
                }
                else if (product - rects.front().rect_tar < 2){
                    break;
                }
                else{
                    for (; i < rects.front().left + rects.front().rect_cols * 2; garden[i][j] = title, ++i);
                    --i;
                    for (; j < rects.front().top + rects.front().rect_rows * 2; garden[i][j] = title, ++j);
                    --j;
                    for (; i >= rects.front().left; garden[i][j] = title, --i);
                    ++i;
                    for (; j >= rects.front().top; garden[i][j] = title, --j);
                    ++j;
                    ++title;
                    rects.push({i + 1, j + 1, rects.front().rect_rows - 1, rects.front().rect_cols - 1, rects.front().rect_tar - 1});
                }
                rects.pop();
            }
            if (rects.empty()){
                printf("YES\n");
                for (int i = 0; i < rows; ++i){
                    for (int j = 0; j < cols; ++j){
                        printf("%hd ", garden[i][j]);
                    }
                    printf("\n");
                }
            }
            else{
                printf("NO\n");
            }
        }
        else{
            printf("NO\n");
        }
        --tests;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%d", &tests);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf("%d%d%d", &rows, &cols, &target);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 18
• Subtask 5: 0 / 39
• Subtask 6: 0 / 22