結果

問題 No.1346 Rectangle
ユーザー qwewe
提出日時 2025-05-14 12:59:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,690 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 67,856 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:00:45
合計ジャッジ時間 1,439 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

int main() {
    // Optimize standard input/output operations for faster execution.
    // std::ios_base::sync_with_stdio(false) disables synchronization with C standard streams.
    // std::cin.tie(NULL) unties cin from cout, allowing input and output operations to not wait for each other.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long N; // Declare a variable N of type long long to store the input dimension. Max N is 10^18.
    
    // Read the value of N from standard input.
    std::cin >> N;
    
    long long M; // Declare a variable M of type long long to store the result.
    
    // Determine the maximum value of M based on N.
    // The problem asks for the maximum M such that an N x M grid can be colored with two colors (e.g., black and white)
    // without forming a monochromatic rectangle. A monochromatic rectangle is defined by four cells
    // (x1, y1), (x1, y2), (x2, y1), (x2, y2) with x1 < x2 and y1 < y2, all having the same color.
    // This condition is equivalent to finding the maximum number of distinct binary column vectors of length N
    // such that for any pair of distinct vectors u, v in the set, the number of positions where both are 1 is at most 1,
    // and the number of positions where both are 0 is at most 1.
    
    // Through analysis and known results in combinatorics (related to Zarankiewicz problem and coding theory bounds):
    // For N=2, the maximum M is 4. All 2^2 = 4 possible columns can be used.
    // For N=3, the maximum M is 6. This can be achieved using all columns of weight 1 and weight 2. binom(3,1) + binom(3,2) = 3 + 3 = 6.
    // For N=4, the maximum M is 6. This can be achieved using all columns of weight 2. binom(4,2) = 6.
    // For N=5, the maximum M is 4. This is suggested by sample output and analysis shows M=5 is likely impossible. Derived bounds give M <= 5.
    // For N=6, derived bounds give M <= 5, but analysis suggests M=5 is impossible. M=4 is likely correct.
    // For N>=7, derived bounds show M <= 4. Since M=4 is achievable (e.g., for N=5 and likely extendable), M=4 is the maximum.
    
    // Thus, the pattern emerges: M=4 for N=2, M=6 for N=3, M=6 for N=4, and M=4 for all N>=5.
    
    if (N == 2) {
        M = 4;
    } else if (N == 3) {
        M = 6;
    } else if (N == 4) {
        M = 6;
    } else { // This case handles N >= 5, including very large N up to 10^18.
        M = 4;
    }
    
    // Output the calculated maximum value of M to standard output, followed by a newline character.
    std::cout << M << std::endl;
    
    // Return 0 to indicate successful execution of the program.
    return 0;
}
0