#include #include #include #include #include #include #include // 内部定数 #define D_ARRAY_MAX 100005 // 最大配列数 #define D_TREE_MAX 1000000 // 木の最大データ数 #define D_TREE_WCNT 2 // 木の方向数 #define D_TREE_LEFT 0 // 木の方向 - 左側 #define D_TREE_RIGHT 1 // 木の方向 - 右側 // 内部構造体 - 木構造 typedef struct Tree { int miSNo, miENo; // 範囲 int miRes; // 結果 int mi1Height[D_TREE_WCNT]; // 木の高さ struct Tree *mzp1Child[D_TREE_WCNT]; // 子 } Tree; // 内部変数 static FILE *szpFpI; // 入力 static double sd1Array[D_ARRAY_MAX]; // 配列 static double sd1Sum[D_ARRAY_MAX]; // 累積和 static int siACnt; // 配列数 static Tree sz1Tree[D_TREE_MAX]; // 木の実データ static int siTCnt; // 木の実データ数 static Tree *szpTop; // 先頭の木データ // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; static int siTNo; #endif // 出力 int fOut( char *pcpLine // 1行 ) { char lc1Buf[1024]; #ifdef D_TEST fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, pcpLine)) { siRes = -1; } #else printf("%s", pcpLine); #endif return 0; } // ソート関数 - double昇順 int fSortFnc( const void *pzpVal1 // 値1 , const void *pzpVal2 // 値2 ) { double *ldpVal1 = (double *)pzpVal1; double *ldpVal2 = (double *)pzpVal2; // double昇順 if (*ldpVal1 > *ldpVal2) { return 1; } else if (*ldpVal1 < *ldpVal2) { return -1; } return 0; } // 検索 // 戻り値:[>=0]配列番号 [-1]なし int fBSrhMPNK( double pdVal // 値 , double *pdpArray // 配列 , int piACnt // 配列数 ) { // 初期範囲 int liSNo = 0; int liENo = piACnt - 1; // 検索 while (1) { // 中間位置 int liMNo = (liSNo + liENo) / 2; // 比較 int liWay; if (pdVal == pdpArray[liMNo]) { // 一致 liWay = -1; } else { // 不一致 if (pdVal < pdpArray[liMNo]) { // 左側へ liWay = -1; } else { // 右側へ liWay = 1; } } // 次の方向 if (liWay < 0) { // 左側へ if (liSNo < liMNo) { // 範囲あり liENo = liMNo - 1; } else { // 範囲なし return liMNo - 1; } } else { // 右側へ if (liENo > liMNo) { // 範囲あり liSNo = liMNo + 1; } else { // 範囲なし return liMNo; } } } return -1; } // 木データ - 作成 Tree * fTreeMake( int piSNo // 範囲 - 開始 1~ , int piENo // 範囲 - 終了 1~ , int piRes // 結果 ) { // 対象の木データ Tree *lzpTree = &(sz1Tree[siTCnt]); siTCnt++; // データセット memset(lzpTree, 0, sizeof(Tree)); // 初期化 lzpTree->miSNo = piSNo; // 範囲 - 開始 lzpTree->miENo = piENo; // 範囲 - 終了 lzpTree->miRes = piRes; // 結果 return lzpTree; } // 木データ - 比較 - 範囲昇順 int fTreeCmp( Tree *pzpTree // 木データ , int piSNo // 範囲 - 開始 1~ , int piENo // 範囲 - 終了 1~ ) { // 範囲昇順 if (piSNo < pzpTree->miSNo) { // 左側 return -1; } else if (piSNo > pzpTree->miSNo) { // 右側 return 1; } if (piENo < pzpTree->miENo) { // 左側 return -1; } else if (piENo > pzpTree->miENo) { // 右側 return 1; } return 0; } // 木データ - 検索 Tree * fTreeSrh( int piSNo // 範囲 - 開始 1~ , int piENo // 範囲 - 終了 1~ ) { // 先頭の木データ Tree *lzpNow = szpTop; // 検索 while (1) { // データ有無 if (lzpNow == NULL) { return NULL; } // 比較 int liRet = fTreeCmp(lzpNow, piSNo, piENo); if (liRet == 0) { // 一致 return lzpNow; } // 子へ移動 if (liRet < 0) { // 左側 lzpNow = lzpNow->mzp1Child[D_TREE_LEFT]; } else { // 右側 lzpNow = lzpNow->mzp1Child[D_TREE_RIGHT]; } } return NULL; } // 木データ - 高さ取得 int fTreeGetHeight( Tree *pzpTree // 対象の木情報 ) { // データ有無 if (pzpTree == NULL) { return 0; } if (pzpTree->mi1Height[D_TREE_LEFT] >= pzpTree->mi1Height[D_TREE_RIGHT]) { return pzpTree->mi1Height[D_TREE_LEFT] + 1; } else { return pzpTree->mi1Height[D_TREE_RIGHT] + 1; } } // 木データ - 右回転(親は子の右下へ・子は親の左上へ) int fTreeRttR( Tree **pzppTree // 回転対象 ) { // 現在の子 Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_LEFT]; // 右回転 (*pzppTree)->mzp1Child[D_TREE_LEFT] = lzpChild->mzp1Child[D_TREE_RIGHT]; // 親の左側 = 子の右側 (*pzppTree)->mi1Height[D_TREE_LEFT] = lzpChild->mi1Height[D_TREE_RIGHT]; // 親の高さ(左) = 子の高さ(右) lzpChild->mzp1Child[D_TREE_RIGHT] = *pzppTree; // 子の右側 = 親 lzpChild->mi1Height[D_TREE_RIGHT] = fTreeGetHeight(*pzppTree); // 子の高さ(右) - 親の高さ *pzppTree = lzpChild; // 親 = 子 return 0; } // 木データ - 左回転(親は子の左下へ・子は親の右上へ) int fTreeRttL( Tree **pzppTree // 回転対象 ) { // 現在の子 Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_RIGHT]; // 左回転 (*pzppTree)->mzp1Child[D_TREE_RIGHT] = lzpChild->mzp1Child[D_TREE_LEFT]; // 親の右側 = 子の左側 (*pzppTree)->mi1Height[D_TREE_RIGHT] = lzpChild->mi1Height[D_TREE_LEFT]; // 親の高さ(右) = 子の高さ(左) lzpChild->mzp1Child[D_TREE_LEFT] = *pzppTree; // 子の左側 = 親 lzpChild->mi1Height[D_TREE_LEFT] = fTreeGetHeight(*pzppTree); // 子の高さ(左) - 親の高さ *pzppTree = lzpChild; // 親 = 子 return 0; } // 木データ - 追加・削除の共通処理 // 戻り値:[1]高さの変更あり [0]高さの変更なし int fTreeComAddDel( Tree **pzppNow // 現在の木情報 , int piWay // 対象の方向 ) { // 高さの変更があるかチェック int liNew = fTreeGetHeight((*pzppNow)->mzp1Child[piWay]); if ((*pzppNow)->mi1Height[piWay] == liNew) { // 変化なし return 0; } (*pzppNow)->mi1Height[piWay] = liNew; // 更新 // 高さが離れている場合、回転 if ((*pzppNow)->mi1Height[D_TREE_LEFT] - (*pzppNow)->mi1Height[D_TREE_RIGHT] > 1) { // 左側が高い fTreeRttR(pzppNow); // 右回転 } else if ((*pzppNow)->mi1Height[D_TREE_RIGHT] - (*pzppNow)->mi1Height[D_TREE_LEFT] > 1) { // 右側が高い fTreeRttL(pzppNow); // 左回転 } return 1; } // 木データ - 追加 // 戻り値:[1]高さの変更あり [0]高さの変更なし [-1]追加なし int fTreeAdd( Tree **pzppNow // 現在の木情報 , int piSNo // 範囲 - 開始 1~ , int piENo // 範囲 - 終了 1~ , int piRes // 結果 ) { // 作成 if (*pzppNow == NULL) { *pzppNow = fTreeMake(piSNo, piENo, piRes); return 1; } // 比較 int liRet = fTreeCmp(*pzppNow, piSNo, piENo); // 一致 if (liRet == 0) { return -1; } // 方向の判別 int liWay; if (liRet < 0) { // 左側 liWay = D_TREE_LEFT; } else { // 右側 liWay = D_TREE_RIGHT; } // 下位へ liRet = fTreeAdd(&((*pzppNow)->mzp1Child[liWay]), piSNo, piENo, piRes); if (liRet < 1) { // 高さの変更なし or 追加なし return liRet; } // 追加・削除の共通処理 return fTreeComAddDel(pzppNow, liWay); } // 判定 int fJudge( int piSNo // 範囲 - 開始 1~ , int piENo // 範囲 - 終了 1~ ) { int liRet; // 判定済 Tree *lzpTree = fTreeSrh(piSNo, piENo); if (lzpTree != NULL) { return lzpTree->miRes; } // 平均値 double ldAvg = (sd1Sum[piENo] - sd1Sum[piSNo - 1]) / (double)(piENo - piSNo + 1); // 平均値未満 - 検索 int liRes = 0; int liNo = fBSrhMPNK(ldAvg, sd1Array, siACnt); if (liNo >= piSNo) { liRet = fJudge(piSNo, liNo); if (liRet == 0) { liRet = fJudge(liNo + 1, piENo); if (liRet == 0) { liRes = -1; } } } // 結果 - 登録 fTreeAdd(&szpTop, piSNo, piENo, liRes); return liRes; } // 実行メイン int fMain( ) { int i; char lc1Buf[1024]; // 配列数 - 取得 fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &siACnt); // 配列 - 取得 sd1Array[0] = 0; for (i = 1; i <= siACnt; i++) { fscanf(szpFpI, "%lf", &sd1Array[i]); } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); // 配列 - ソート qsort(sd1Array, siACnt + 1, sizeof(double), fSortFnc); // 累積和 - セット sd1Sum[0] = 0; for (i = 1; i <= siACnt; i++) { sd1Sum[i] = sd1Sum[i - 1] + sd1Array[i]; } // 判定 return fJudge(1, siACnt); } // 1回実行 int fOne( ) { int liRet; char lc1Buf[1024]; // データ - 初期化 siTCnt = 0; // 木の実データ数 szpTop = NULL; // 先頭の木データ // 入力 - セット #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 // 実行メイン liRet = fMain(); // 出力 if (liRet == 0) { sprintf(lc1Buf, "First\n"); } else { sprintf(lc1Buf, "Second\n"); } 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; }