結果

問題 No.800 四平方定理
ユーザー asugen0402
提出日時 2019-05-15 13:47:48
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1,311 ms / 2,000 ms
コード長 3,987 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 33,024 KB
実行使用メモリ 30,384 KB
最終ジャッジ日時 2024-09-13 23:26:58
合計ジャッジ時間 17,564 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_ARRAY_MAX     4000000                                 // 最大配列数
// 内部変数
static FILE *szpFpI;                                            // 入力
static int si1Array[D_ARRAY_MAX];                               // 配列
static int siACnt;                                              // 配列数
// 内部変数 - テスト用
#ifdef D_TEST
    static int siRes;
    static FILE *szpFpA;
    static int siTNo;
#endif
// 出力
int
fOut(
    char *pcpLine               // <I> １行
)
{
    char lc1Buf[1024];
#ifdef D_TEST
    fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
    if (strcmp(lc1Buf, pcpLine)) {
        siRes = -1;
    }
#else
    printf("%s", pcpLine);
#endif
    return 0;
}
// ソート関数 - int昇順
int
fSortFnc(
    const void *pzpVal1         // <I> 値１
    , const void *pzpVal2       // <I> 値２
)
{
    int *lipVal1 = (int *)pzpVal1;
    int *lipVal2 = (int *)pzpVal2;
    // int昇順
    if (*lipVal1 > *lipVal2) {
        return 1;
    }
    else if (*lipVal1 < *lipVal2) {
        return -1;
    }
    return 0;
}
// 検索(値の重複可・範囲取得)
// 戻り値：[>=0]配列番号 [-1]なし
int
fBSrhMK(
    int piVal                   // <I> 値
    , int *pipArray             // <I> 配列
    , int piACnt                // <I> 配列数
    , int piWay                 // <I> 方向 [1]右側 or [-1]左側
)
{
    // 初期範囲
    int liSNo = 0;
    int liENo = piACnt - 1;
    // 検索
    int liNo = -1;
    while (1) {
        // 中間位置
        int liMNo = (liSNo + liENo) / 2;
        // 比較
        if (piVal == pipArray[liMNo]) {             // 一致
            liNo = liMNo;
            // 次の方向
            if (piWay < 0) {                            // 左側へ
                liENo = liMNo - 1;
            }
            else {                                      // 右側へ
                liSNo = liMNo + 1;
            }
        }
        else {                                      // 不一致
            if (piVal < pipArray[liMNo]) {              // 左側へ
                liENo = liMNo - 1;
            }
            else {                                      // 右側へ
                liSNo = liMNo + 1;
            }
        }
        // 範囲チェック
        if (liSNo > liENo) {
            return liNo;
        }
    }
    return -1;
}
int
fBSrhM(
    int piVal                   // <I> 値
    , int *pipArray             // <I> 配列
    , int piACnt                // <I> 配列数
    , int *pipPNo               // <O> [>=0]開始 [-1]なし
    , int *pipNNo               // <O> [>=0]終了 [-1]なし
)
{
    // 左側へ
    *pipPNo = fBSrhMK(piVal, pipArray, piACnt, -1);
    if (*pipPNo < 0) {
        *pipNNo = -1;
        return -1;
    }
    // 右側へ
    *pipNNo = fBSrhMK(piVal, pipArray, piACnt, 1);
    return 0;
}
// 実行メイン
long long
fMain(
)
{
    int i, j;
    char lc1Buf[1024];
    // N, D - 取得
    int liN, liD;
    fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
    sscanf(lc1Buf, "%d%d", &liN, &liD);
    // wの2乗 + D - zの2乗
    siACnt = 0;
    for (i = 1; i <= liN; i++) {
        for (j = 1; j <= liN; j++) {
            si1Array[siACnt] = i * i + liD - j * j;
            siACnt++;
        }
    }
    // 配列 - ソート
    qsort(si1Array, siACnt, sizeof(int), fSortFnc);
    // 個数 - 取得
    long long llCnt = 0;
    for (i = 1; i <= liN; i++) {
        for (j = 1; j <= liN; j++) {
            int liXY = i * i + j * j;
            // 検索
            int liPNo, liNNo;
            fBSrhM(liXY, si1Array, siACnt, &liPNo, &liNNo);
            if (liPNo >= 0) {
                llCnt += liNNo - liPNo + 1;
            }
        }
    }
    return llCnt;
}
// １回実行
int
fOne(
)
{
    long long llRet;
    char lc1Buf[1024];
    // 入力 - セット
#ifdef D_TEST
    sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
    szpFpI = fopen(lc1Buf, "r");
    sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
    szpFpA = fopen(lc1Buf, "r");
    siRes = 0;
#else
    szpFpI = stdin;
#endif
    // 実行メイン
    llRet = fMain();
    // 出力
    sprintf(lc1Buf, "%lld\n", llRet);
    fOut(lc1Buf);
    // 残データ有無
#ifdef D_TEST
    lc1Buf[0] = '\0';
    fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
    if (strcmp(lc1Buf, "")) {
        siRes = -1;
    }
#endif
    // テストファイルクローズ
#ifdef D_TEST
    fclose(szpFpI);
    fclose(szpFpA);
#endif
    // テスト結果
#ifdef D_TEST
    if (siRes == 0) {
        printf("OK %d\n", siTNo);
    }
    else {
        printf("NG %d\n", siTNo);
    }
#endif
    return 0;
}
// プログラム開始
int
main()
{
#ifdef D_TEST
    int i;
    for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
        siTNo = i;
        fOne();
    }
#else
    fOne();
#endif
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0