Submission #8006592
Source Code Expand
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_TREE_MAX 100000 // 木の最大データ数
#define D_TREE_WCNT 2 // 木の方向数
#define D_TREE_LEFT 0 // 木の方向 - 左側
#define D_TREE_RIGHT 1 // 木の方向 - 右側
// 内部構造体 - 木構造
typedef struct Tree {
long long mlVal; // 能力
int mi1Height[D_TREE_WCNT]; // 木の高さ
struct Tree *mzp1Child[D_TREE_WCNT]; // 子
} Tree;
// 内部変数
static FILE *szpFpI; // 入力
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
// 1行出力
int
fOutLine(
char *pcpLine // <I> 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;
}
// 木データ - 作成
Tree *
fTreeMake(
long long plVal // <I> 能力
)
{
// 対象の木データ
Tree *lzpTree = &(sz1Tree[siTCnt]);
siTCnt++;
// データセット
memset(lzpTree, 0, sizeof(Tree)); // 初期化
lzpTree->mlVal = plVal;
return lzpTree;
}
// 木データ - 比較 - 能力昇順
int
fTreeCmp(
Tree *pzpTree // <I> 木データ
, long long plVal // <I> 能力
)
{
// 能力昇順
if (plVal < pzpTree->mlVal) { // 左側
return -1;
}
else if (plVal > pzpTree->mlVal) { // 右側
return 1;
}
return 0;
}
// 木データ - 検索 - 指定値 or 指定値に近い値
Tree *
fTreeSrhRng(
int piMode // <I> [-1]以下 or [1]以上
, long long plVal // <I> 能力
)
{
// 先頭の木データ
Tree *lzpNow = szpTop;
// 検索
Tree *lzpNear = NULL;
while (1) {
// データ有無
if (lzpNow == NULL) {
return lzpNear;
}
// 比較
int liRet = fTreeCmp(lzpNow, plVal);
// 一致
if (liRet == 0) { // 一致
return lzpNow;
}
// 子へ移動
if (liRet < 0) { // 左側
// 対象値に近い値更新
if (piMode > 0) { // 以上
lzpNear = lzpNow;
}
lzpNow = lzpNow->mzp1Child[D_TREE_LEFT];
}
else { // 右側
// 対象値に近い値更新
if (piMode < 0) { // 以下
lzpNear = lzpNow;
}
lzpNow = lzpNow->mzp1Child[D_TREE_RIGHT];
}
}
return NULL;
}
// 木データ - 高さ取得
int
fTreeGetHeight(
Tree *pzpTree // <I> 対象の木情報
)
{
// データ有無
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 // <I> 回転対象
)
{
// 現在の子[左]
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 // <I> 回転対象
)
{
// 現在の子[右]
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;
}
// 木データ - 追加・削除の共通処理
// 戻り値:[2]高さの変更あり [1]高さの変更なし
int
fTreeComAddDel(
Tree **pzppNow // <I> 現在の木情報
, int piWay // <I> 対象の方向
)
{
// 高さの変更があるかチェック
int liNew = fTreeGetHeight((*pzppNow)->mzp1Child[piWay]);
if ((*pzppNow)->mi1Height[piWay] == liNew) { // 変化なし
return 1;
}
(*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 2;
}
// 木データ - 追加
// 戻り値:[2]高さの変更あり [1]高さの変更なし [0]データ数の追加のみ
int
fTreeAdd(
Tree **pzppNow // <I> 現在の木情報
, long long plVal // <I> 能力
)
{
// 作成
if (*pzppNow == NULL) {
*pzppNow = fTreeMake(plVal);
return 2;
}
// 比較
int liRet = fTreeCmp(*pzppNow, plVal);
// 一致
if (liRet == 0) {
return 0;
}
// 方向の判別
int liWay;
if (liRet < 0) { // 左側
liWay = D_TREE_LEFT;
}
else { // 右側
liWay = D_TREE_RIGHT;
}
// 下位へ
liRet = fTreeAdd(&((*pzppNow)->mzp1Child[liWay]), plVal);
if (liRet < 2) { // 高さの変更あり以外
return liRet;
}
// 追加・削除の共通処理
return fTreeComAddDel(pzppNow, liWay);
}
// 実行メイン
long long
fMain(
)
{
int i;
char lc1Buf[1024];
// 人数・能力 - 取得
int liHCnt;
long long llVal;
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d%lld", &liHCnt, &llVal);
// 初期能力 - 追加
fTreeAdd(&szpTop, llVal);
// 能力 - 取得
long long llSum = 0;
for (i = 0; i < liHCnt; i++) {
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%lld", &llVal);
// 検索 - 以下
long long llDF1;
Tree *lzpTree = fTreeSrhRng(-1, llVal);
if (lzpTree == NULL) {
llDF1 = LLONG_MAX;
}
else {
llDF1 = llVal - lzpTree->mlVal;
}
// 検索 - 以上
long long llDF2;
lzpTree = fTreeSrhRng(1, llVal);
if (lzpTree == NULL) {
llDF2 = LLONG_MAX;
}
else {
llDF2 = lzpTree->mlVal - llVal;
}
// 合計 - 加算
if (llDF1 < llDF2) {
llSum += llDF1;
}
else {
llSum += llDF2;
}
// 能力 - 追加
fTreeAdd(&szpTop, llVal);
}
return llSum;
}
// 1回実行
int
fOne(
)
{
long long llRet;
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
// 実行メイン
llRet = fMain();
// 出力
sprintf(lc1Buf, "%lld\n", llRet);
fOutLine(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;
}
Submission Info
Compile Error
./Main.c: In function ‘fMain’:
./Main.c:276:2: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
^
./Main.c:285:3: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
^
Judge Result
Set Name |
all |
Score / Max Score |
500 / 500 |
Status |
|
Set Name |
Test Cases |
all |
subtask0_sample01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
1 ms |
128 KB |
subtask1_01.txt |
AC |
1 ms |
128 KB |
subtask1_02.txt |
AC |
1 ms |
128 KB |
subtask1_03.txt |
AC |
1 ms |
128 KB |
subtask1_04.txt |
AC |
63 ms |
3328 KB |
subtask1_05.txt |
AC |
63 ms |
3328 KB |
subtask1_06.txt |
AC |
63 ms |
3328 KB |
subtask1_07.txt |
AC |
63 ms |
3328 KB |
subtask1_08.txt |
AC |
63 ms |
3328 KB |
subtask1_09.txt |
AC |
63 ms |
3328 KB |
subtask1_10.txt |
AC |
76 ms |
3328 KB |
subtask1_11.txt |
AC |
63 ms |
3328 KB |
subtask1_12.txt |
AC |
63 ms |
3328 KB |
subtask1_13.txt |
AC |
63 ms |
3328 KB |
subtask1_14.txt |
AC |
19 ms |
128 KB |
subtask1_15.txt |
AC |
40 ms |
3328 KB |