Submission #346587

#	Time	Username	Problem	Language	Result	Execution time	Memory
346587		jamezzz	Square or Rectangle? (NOI19_squarerect)	C++14	100 / 100	1 ms	364 KiB

squarerect

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

int n;
bool inside[5][5];

bool myIns(int i, int j){
    if (i <= 0 || j <= 0 || i > n || j > n) return false;
    else return inside_shape(i, j);
}

bool am_i_square(int N, int Q) {
    memset(inside, false, sizeof inside);
    n = N;
    bool found = 0;
    for (int i = 0; i < 4; ++i){
        for (int j = 0; j < 4; ++j){
            inside[i][j] = myIns((i + 1) * 20, (j + 1) * 20);
            found = found || inside[i][j];
        }
    }
    if (!found){
        int cnt = 0, x = 0, y = 0;
        for (int i = 0; i < 5; ++i){
            inside[i][4] = myIns((i + 1) * 20, 100);
            cnt += inside[i][4];
            if (inside[i][4]){ x = i; y = 4; }
        }
        for (int i = 0; i < 4; ++i){
            inside[4][i] = myIns(100, (i + 1) * 20);
            cnt += inside[4][i];
            if (inside[4][i]){ x = 4; y = i; }
        }
        if (cnt != 1) return false;
        if (x == 4){ //bottom
            int lo = y * 20, hi = (y + 1) * 20, mid, res;
            while (lo <= hi){
                mid = (lo + hi) / 2;
                if (myIns(100, mid)) hi = mid - 1;
                else{ lo = mid + 1; res = mid + 1; }
            }
            return (myIns(100, res + 19) && !myIns(100, res + 20));
        }
        else{
            int lo = x * 20, hi = (x + 1) * 20, mid, res;
            while (lo <= hi){
                mid = (lo + hi) / 2;
                if (myIns(mid, 100)) hi = mid - 1;
                else{ lo = mid + 1; res = mid + 1; }
            }
            return (myIns(res + 19, 100) && !myIns(res + 20, 100));
        }
    }
    else{
        int minx = 100, miny = 100, maxx = 0, maxy = 0;
        for (int i = 0; i < 4; ++i){
            for (int j = 0; j < 4; ++j){
                if (inside[i][j]){
                    minx = min(minx, i);
                    maxx = max(maxx, i);
                    miny = min(miny, j);
                    maxy = max(maxy, j);
                }
            }
        }
        int lo = minx * 20, hi = (minx + 1) * 20, mid, res;
        while (lo <= hi){
            mid = (lo + hi) / 2;
            if (myIns(mid, (miny + 1) * 20)) hi = mid - 1;
            else{ lo = mid + 1; res = mid + 1; }
        }
        int top = res;
        lo = (maxx + 1) * 20; hi = (maxx + 2) * 20 + 1;
        while (lo <= hi){
            mid = (lo + hi) / 2;
            if (myIns(mid, (miny + 1) * 20)){
                lo = mid + 1; res = mid;
            }
            else hi = mid - 1;
        }
        int bot = res;
        lo = miny * 20; hi = (miny + 1) * 20;
        while (lo <= hi){
            mid = (lo + hi) / 2;
            if (myIns((minx + 1) * 20, mid)) hi = mid - 1;
            else{ lo = mid + 1; res = mid + 1; }
        }
        int lft = res;
        int sze = bot - top;
        int rght = lft + sze;
        return (myIns((minx + 1) * 20, rght) && !myIns((minx + 1) * 20, rght + 1));
    }
}

Compilation message (stderr)

squarerect.cpp: In function 'bool am_i_square(int, int)':
squarerect.cpp:67:56: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |         int lo = minx * 20, hi = (minx + 1) * 20, mid, res;
      |                                                        ^~~
squarerect.cpp:52:51: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |             return (myIns(res + 19, 100) && !myIns(res + 20, 100));
      |                                              ~~~~~^~~~~~~~~~~~~~~
squarerect.cpp:43:51: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |             return (myIns(100, res + 19) && !myIns(100, res + 20));
      |                                              ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 18 / 18
• Subtask 4: 49 / 49