Submission #1218987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218987		takoshanava	Square or Rectangle? (NOI19_squarerect)	C++20	100 / 100	0 ms	324 KiB

squarerect

#include <bits/stdc++.h>
#include "squarerect.h"
//#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

bool am_i_square(int N, int Q) {
    int used = 0;
    int mn = (N * N + 24) / 25;
    int ms = (int)ceil(sqrt(mn));

    int x = N, y = N;
    bool found = false;
    for (int i = ms; i <= N and !found; i += ms) {
        for (int j = ms; j < i and !found; j += ms) {
            if (used++, inside_shape(i, j)) {
                x = i; y = j;
                found = true;
                break;
            }
            if (used++, inside_shape(j, i)) {
                x = j; y = i;
                found = true;
                break;
            }
        }
        if (found) break;
        if (N < i + ms) break;
        if (used++, inside_shape(i, i)) {
            x = i; y = i;
            found = true;
            break;
        }
    }

    int l = x - ms + 1, r = min(x, N - ms + 2);
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (used++, inside_shape(mid, y)) r = mid;
        else l = mid + 1;
    }
    x = l;

    if (N < x + ms - 1) return false;

    l = y - ms + 1, r = min(y, N - ms + 2);
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (used++, inside_shape(x, mid)) r = mid;
        else l = mid + 1;
    }
    y = l;

    if (N < y + ms - 1) return false;

    l = ms - 1;
    r = min(N - x, N - y) + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (used++, !inside_shape(x + mid, y + mid)) r = mid;
        else l = mid + 1;
    }

    int side = l;
    bool valid = side != ms - 1;

    if (valid and x + side - 1 <= N and y + side <= N)
        valid &= !inside_shape(x + side - 1, y + side);
    if (valid and x + side <= N and y + side - 1 <= N)
        valid &= !inside_shape(x + side, y + side - 1);

    return valid;
}

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