結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
コンテスト
ユーザー asugen0402
提出日時 2019-04-08 13:32:23
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 103 ms / 4,000 ms
コード長 8,839 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 34,432 KB
実行使用メモリ 9,580 KB
最終ジャッジ日時 2024-07-01 22:51:28
合計ジャッジ時間 5,449 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_TEAM_MAX		100000									// 最大チーム数
#define D_UNI_MAX		100000									// 最大大学数
#define D_SEGT_CNT		131072									// セグメントツリーデータ数(2の累乗)

// 内部構造体 - チーム情報
typedef struct Team {
	int miTNo;													// チーム番号 0～
	int miACnt;													// 解いた問題の数
	int miPVal;													// ペナルティ
	int miUni;													// 大学
	int miSCNo;													// セグメントツリー位置 0～
	int miSNo;													// 選抜番号 0～
} Team;

// 内部構造体 - 大学情報
typedef struct Uni {
	int miSCnt;													// 選抜数
	int miSNo, miENo;											// チーム範囲
} Uni;

// 内部変数
static FILE *szpFpI;											// 入力
static Team sz1Team[D_TEAM_MAX];								// チーム
static int siTCnt;												// チーム数
static int siSCnt;												// 選抜数
static Uni sz1Uni[D_UNI_MAX + 5];								// 大学
static Team *szp1SegT[D_SEGT_CNT * 2];							// セグメントツリー
static int siSCNo;												// セグメントツリー - 子の開始位置

// 内部変数 - テスト用
#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
fSortFncAdUu(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Team *lzpVal1 = (Team *)pzpVal1;
	Team *lzpVal2 = (Team *)pzpVal2;

	// 解いた問題の数降順
	if (lzpVal1->miACnt > lzpVal2->miACnt) {
		return -1;
	}
	else if (lzpVal1->miACnt < lzpVal2->miACnt) {
		return 1;
	}

	// 大学昇順
	if (lzpVal1->miUni > lzpVal2->miUni) {
		return 1;
	}
	else if (lzpVal1->miUni < lzpVal2->miUni) {
		return -1;
	}

	return 0;
}

// ソート関数 - 選抜番号昇順
int
fSortFncSu(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Team *lzpVal1 = (Team *)pzpVal1;
	Team *lzpVal2 = (Team *)pzpVal2;

	// 選抜番号昇順
	if (lzpVal1->miSNo > lzpVal2->miSNo) {
		return 1;
	}
	else if (lzpVal1->miSNo < lzpVal2->miSNo) {
		return -1;
	}

	return 0;
}

// セグメントツリー - 子の開始位置 - セット
int
fSegTSetCSNo(
	int piCnt					// <I> 子データ数
)
{
	siSCNo = 1;
	while (siSCNo < piCnt) {
		siSCNo *= 2;
	}

	return 0;
}

// セグメントツリー - 子の処理 - 選抜数[大学]昇順 - ペナルティ昇順
int
fSegTCProc(
	int piNo1					// <I> 位置１ 0～
	, int piNo2					// <I> 位置２ 0～
)
{
	// データ有無
	if (szp1SegT[piNo1] == NULL) {
		return piNo2;
	}
	if (szp1SegT[piNo2] == NULL) {
		return piNo1;
	}

	// 選抜済
	if (szp1SegT[piNo1]->miPVal == INT_MAX) {
		return piNo2;
	}
	if (szp1SegT[piNo2]->miPVal == INT_MAX) {
		return piNo1;
	}

	// 選抜数[大学]昇順
	int liUni1 = szp1SegT[piNo1]->miUni;
	int liUni2 = szp1SegT[piNo2]->miUni;
	if (sz1Uni[liUni1].miSCnt < sz1Uni[liUni2].miSCnt) {
		return piNo1;
	}
	else if (sz1Uni[liUni1].miSCnt > sz1Uni[liUni2].miSCnt) {
		return piNo2;
	}

	// ペナルティ昇順
	if (szp1SegT[piNo1]->miPVal < szp1SegT[piNo2]->miPVal) {
		return piNo1;
	}
	else if (szp1SegT[piNo1]->miPVal > szp1SegT[piNo2]->miPVal) {
		return piNo2;
	}

	return piNo1;
}

// セグメントツリー - 親データセット
int
fSegTSetPData(
)
{
	int i;

	// 最初の親番号範囲
	int liPNo1 = siSCNo / 2;
	int liPNo2 = siSCNo - 1;

	// 作成
	while (liPNo1 > 0) {
		for (i = liPNo1; i <= liPNo2; i++) {

			// 対象の子を取得
			int liCNo = fSegTCProc(i * 2, i * 2 + 1);

			// セット
			szp1SegT[i] = szp1SegT[liCNo];
		}

		// 次の親番号範囲
		liPNo2 = liPNo1 - 1;
		liPNo1 /= 2;
	}

	return 0;
}

// セグメントツリー - 更新 - １データ
int
fSegTUpOne(
	int piUpNo					// <I> 更新位置 0～
	, int piVal					// <I> 更新値
)
{
	// 子番号
	int liCNo1 = siSCNo + piUpNo;
	int liCNo2;
	if (liCNo1 % 2 == 0) {
		liCNo2 = liCNo1 + 1;
	}
	else {
		liCNo2 = liCNo1 - 1;
	}

	// 更新
	szp1SegT[liCNo1]->miPVal = piVal;

	// 親を更新
	while (1) {

		// 親番号
		int liPNo = liCNo1 / 2;
		if (liPNo < 1) {
			break;
		}

		// 対象の子を取得
		int liCNo = fSegTCProc(liCNo1, liCNo2);

		// 更新
		szp1SegT[liPNo] = szp1SegT[liCNo];

		// 次の子番号
		liCNo1 = liPNo;
		if (liCNo1 % 2 == 0) {
			liCNo2 = liCNo1 + 1;
		}
		else {
			liCNo2 = liCNo1 - 1;
		}
	}

	return 0;
}

// セグメントツリー - 更新 - 範囲
int
fSegTUpRngMain(
	int piUpS					// <I> 更新範囲 - 開始 0～
	, int piUpE					// <I> 更新範囲 - 終了 0～
	, int piNNo					// <I> 現在位置 1～
	, int piNowS				// <I> 現在範囲 - 開始 0～
	, int piNowE				// <I> 現在範囲 - 終了 0～
)
{
	// 範囲外チェック
	if (piUpE < piNowS || piNowE < piUpS) {
		return 0;
	}

	// 範囲内チェック
	if (piUpS <= piNowS && piNowE <= piUpE) {
		return 0;
	}

	// 子番号
	int liCNo1 = piNNo * 2;
	int liCNo2 = liCNo1 + 1;

	// 範囲の半分
	int liHalf = (piNowE - piNowS + 1) / 2;

	// 両側の子へ
	fSegTUpRngMain(piUpS, piUpE, liCNo1, piNowS, piNowS + liHalf - 1);
	fSegTUpRngMain(piUpS, piUpE, liCNo2, piNowE - liHalf + 1, piNowE);

	// 対象の子を取得
	int liCNo = fSegTCProc(liCNo1, liCNo2);

	// 更新
	szp1SegT[piNNo] = szp1SegT[liCNo];

	return 0;
}
int
fSegTUpRng(
	int piUpS					// <I> 更新範囲 - 開始 0～
	, int piUpE					// <I> 更新範囲 - 終了 0～
)
{
	return fSegTUpRngMain(piUpS, piUpE, 1, 0, siSCNo - 1);
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// チーム数・選抜数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siTCnt, &siSCnt);

	// チーム - 取得
	for (i = 0; i < siTCnt; i++) {
		sz1Team[i].miTNo = i;
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Team[i].miACnt, &sz1Team[i].miPVal, &sz1Team[i].miUni);
		sz1Team[i].miUni--;
		sz1Team[i].miSNo = INT_MAX;
	}

	// チーム - ソート
	qsort(sz1Team, siTCnt, sizeof(Team), fSortFncAdUu);

	// 選抜
	int liSCnt = 0;
	int liNo = 0;
	while (liSCnt < siSCnt) {

		// 対象データ数(解いた問題の数が同一)
		int liTCnt = 1;
		for (i = liNo + 1; i < siTCnt; i++) {
			if (sz1Team[i].miACnt == sz1Team[liNo].miACnt) {
				liTCnt++;
			}
			else {
				break;
			}
		}

		// セグメントツリー - 初期化
		memset(szp1SegT, 0, sizeof(szp1SegT));

		// セグメントツリー - 子の開始位置 - セット
		fSegTSetCSNo(liTCnt);

		// セグメントツリー - 子データセット
		int liUni = -1;
		for (i = 0; i < liTCnt; i++) {
			int liTNo = liNo + i;
			szp1SegT[siSCNo + i] = &sz1Team[liTNo];
			szp1SegT[siSCNo + i]->miSCNo = i;
			if (liUni == sz1Team[liTNo].miUni) {
				sz1Uni[liUni].miENo = i;
			}
			else {
				liUni = sz1Team[liTNo].miUni;
				sz1Uni[liUni].miSNo = i;
				sz1Uni[liUni].miENo = i;
			}
		}

		// セグメントツリー - 親データセット
		fSegTSetPData();

		// 選抜
		for (i = 0; i < liTCnt; i++) {

			// 対象チーム
			Team *lzpTeam = szp1SegT[1];
			lzpTeam->miSNo = liSCnt;
			liSCnt++;

			// 選抜済
			fSegTUpOne(lzpTeam->miSCNo, INT_MAX);

			// 選抜数[大学]
			sz1Uni[lzpTeam->miUni].miSCnt++;
			fSegTUpRng(sz1Uni[lzpTeam->miUni].miSNo, sz1Uni[lzpTeam->miUni].miENo);
		}

		// 次回開始番号
		liNo += liTCnt;
	}

	// チーム - ソート
	qsort(sz1Team, siTCnt, sizeof(Team), fSortFncSu);

	// 出力
	for (i = 0; i < siSCnt; i++) {
		sprintf(lc1Buf, "%d\n", sz1Team[i].miTNo);
		fOut(lc1Buf);
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	memset(sz1Uni, 0, sizeof(sz1Uni));							// 大学

	// 入力 - セット
#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();

	// 残データ有無
#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;
}
0