Modern art

input/code.cpp: In function 'int main()':
input/code.cpp:20:40: warning: variable 'min_P_final' set but not used [-Wunused-but-set-variable]
   20 |     int final_w, final_h, protrusions, min_P_final;
      |                                        ^~~~~~~~~~~

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

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, P;
    cin >> A >> P;
    
    // Check if P is within the valid range and (4*A - P) is even
    if(P < 2*A + 2 || (4LL * A - P) < 0 || (4LL * A - P) % 2 != 0){
        cout << "IMPOSSIBLE";
        return 0;
    }
    
    bool possible = false;
    int final_w, final_h, protrusions, min_P_final;
    
    // Iterate over possible rectangle dimensions
    for(int w=1; w<=A && !possible; w++){
        for(int h=1; h<=A/w && !possible; h++){
            if(w*h > A) continue;
            int min_P = 2*(w + h);
            int needed_protrusions = A - w*h;
            // Each protrusion increases perimeter by 2
            int max_P = min_P + 2*needed_protrusions;
            if(P == max_P){
                final_w = w;
                final_h = h;
                protrusions = needed_protrusions;
                min_P_final = min_P;
                possible = true;
            }
        }
    }
    
    if(!possible){
        cout << "IMPOSSIBLE";
        return 0;
    }
    
    int grid_rows = final_h + 2;
    int grid_cols = final_w + 2;
    vector<vector<char>> grid(grid_rows, vector<char>(grid_cols, '0'));
    
    // Fill the initial rectangle
    for(int i=1; i<=final_h; i++) {
        for(int j=1; j<=final_w; j++) {
            grid[i][j] = '1';
        }
    }
    
    ll current_P = 2*(final_w + final_h); // Initialize perimeter correctly
    int added = 0;
    
    // Directions: Up, Down, Left, Right
    vector<pair<int, int>> dirs = { {-1,0}, {1,0}, {0,-1}, {0,1} };
    
    // Attempt to add protrusions to reach the desired perimeter
    for(int i=1; i<=final_h && added < protrusions; i++){
        for(int j=1; j<=final_w && added < protrusions; j++){
            if(added >= protrusions) break;
            // Try to add protrusions to the top
            if(i >1 && grid[i-1][j] == '0'){
                grid[i-1][j] = '1';
                current_P += 2;
                added++;
                continue;
            }
            // Try to add protrusions to the bottom
            if(i < final_h && grid[i+1][j] == '0'){
                grid[i+1][j] = '1';
                current_P += 2;
                added++;
                continue;
            }
            // Try to add protrusions to the left
            if(j >1 && grid[i][j-1] == '0'){
                grid[i][j-1] = '1';
                current_P += 2;
                added++;
                continue;
            }
            // Try to add protrusions to the right
            if(j < final_w && grid[i][j+1] == '0'){
                grid[i][j+1] = '1';
                current_P += 2;
                added++;
                continue;
            }
        }
    }
    
    // After adding protrusions, ensure we have added the required number
    if(added != protrusions){
        cout << "IMPOSSIBLE";
        return 0;
    }
    
    // Determine the bounding box of the figure
    int min_x = grid_rows, max_x = -1, min_y = grid_cols, max_y = -1;
    for(int i=1; i<=final_h; i++) {
        for(int j=1; j<=final_w; j++) {
            if(grid[i][j] == '1'){
                min_x = min(min_x, i);
                max_x = max(max_x, i);
                min_y = min(min_y, j);
                max_y = max(max_y, j);
            }
        }
    }
    
    // Include protrusions in the bounding box
    min_x = max(min_x -1, 0);
    max_x = min(max_x +1, grid_rows-1);
    min_y = max(min_y -1, 0);
    max_y = min(max_y +1, grid_cols-1);
    
    // Extract the subgrid containing the figure
    vector<vector<char>> subgrid;
    for(int i = min_x; i <= max_x; ++i){
        vector<char> row;
        for(int j = min_y; j <= max_y; ++j){
            row.push_back(grid[i][j]);
        }
        subgrid.push_back(row);
    }
    
    int sub_rows = subgrid.size();
    int sub_cols = subgrid[0].size();
    
    // Ensure the boundary of the subgrid is white
    for(int i = 0; i < sub_rows; ++i){
        subgrid[i][0] = '0';
        subgrid[i][sub_cols-1] = '0';
    }
    for(int j = 0; j < sub_cols; ++j){
        subgrid[0][j] = '0';
        subgrid[sub_rows-1][j] = '0';
    }
    
    // Recalculate the perimeter to verify correctness
    ll final_P = 0;
    for(int i=1; i<sub_rows-1; i++){
        for(int j=1; j<sub_cols-1; j++){
            if(subgrid[i][j] == '1'){
                for(auto &[dx, dy] : dirs){
                    int ni = i + dx;
                    int nj = j + dy;
                    if(subgrid[ni][nj] == '0') final_P++;
                }
            }
        }
    }
    
    // Verify if the calculated perimeter matches the desired perimeter
    if(final_P != P){
        cout << "IMPOSSIBLE";
        return 0;
    }
    
    // Output the final grid
    cout << "POSSIBLE\n";
    for(auto &row : subgrid){
        for(auto &c : row) cout << c;
        cout << '\n';
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: ACCEPTED

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: ACCEPTED

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: ACCEPTED

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: ACCEPTED

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: ACCEPTED

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: ACCEPTED

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: ACCEPTED

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: ACCEPTED

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: ACCEPTED

Test 48

Verdict: WRONG ANSWER

Test 49

Verdict: ACCEPTED

Test 50

Verdict: WRONG ANSWER