結果

問題 No.282 おもりと天秤(2)
コンテスト
ユーザー asugen0402
提出日時 2019-03-19 16:59:58
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1,851 ms / 5,000 ms
コード長 4,053 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 25,476 KB
平均クエリ数 267.12
最終ジャッジ日時 2024-07-17 02:08:59
合計ジャッジ時間 19,885 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 内部定数
#define D_ON			1										// 汎用フラグ - ON
#define D_OFF			0										// 汎用フラグ - OFF
#define D_WCNT_MAX		500										// 最大重り数

// 内部構造体 - 重り情報
typedef struct Wgt {
	int miNo;													// 番号 1～
	char mc1Quiz[D_WCNT_MAX];									// 質問[相手の重り]
	int miCnt;													// 傾き数
} Wgt;

// 内部変数
static FILE *szpFpI;											// 入力
static Wgt sz1Wgt[D_WCNT_MAX];									// 重り
static int siWCnt;												// 重り数

// 内部変数 - テスト用
#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);
	fflush(stdout);
#endif

	return 0;
}

// ソート関数 - 傾き数昇順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Wgt *lzpVal1 = (Wgt *)pzpVal1;
	Wgt *lzpVal2 = (Wgt *)pzpVal2;

	// 傾き数昇順
	if (lzpVal1->miCnt > lzpVal2->miCnt) {
		return 1;
	}
	else if (lzpVal1->miCnt < lzpVal2->miCnt) {
		return -1;
	}

	return 0;
}

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

	// 重り数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &siWCnt);

	while (1) {

		// 質問フラグ - 初期化
		char lc1Quiz[D_WCNT_MAX];
		memset(lc1Quiz, D_OFF, sizeof(lc1Quiz));

		// 質問 - 作成
		int liWCnt = 0;
		int li1LNo[D_WCNT_MAX / 2];
		int li1RNo[D_WCNT_MAX / 2];
		for (i = 0; i < siWCnt; i++) {
			if (lc1Quiz[i] != D_OFF) {
				continue;
			}

			// 右側の重り - 取得
			for (j = i + 1; j < siWCnt; j++) {
				if (sz1Wgt[i].mc1Quiz[j] != D_OFF) {
					continue;
				}
				if (lc1Quiz[j] == D_OFF) {
					break;
				}
			}
			if (j >= siWCnt) {
				continue;
			}

			// 質問 - 追加
			li1LNo[liWCnt] = i;
			li1RNo[liWCnt] = j;
			liWCnt++;
			sz1Wgt[i].mc1Quiz[j] = D_ON;
			lc1Quiz[i] = D_ON;
			lc1Quiz[j] = D_ON;
		}
		if (liWCnt < 1) {
			break;
		}

		// 質問
		strcpy(lc1Out, "?");
		for (i = 0; i < liWCnt; i++) {
			sprintf(lc1Buf, " %d %d", li1LNo[i] + 1, li1RNo[i] + 1);
			strcat(lc1Out, lc1Buf);
		}
		for ( ; i < siWCnt; i++) {
			strcat(lc1Out, " 0 0");
		}
		strcat(lc1Out, "\n");
		fOut(lc1Out);

		// 応答
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		for (i = 0; i < liWCnt; i++) {
			if (lc1Buf[i * 2] == '<') {
				sz1Wgt[li1RNo[i]].miCnt++;
			}
			else {
				sz1Wgt[li1LNo[i]].miCnt++;
			}
		}
	}

	// 重り - 番号 - セット
	for (i = 0; i < siWCnt; i++) {
		sz1Wgt[i].miNo = i + 1;
	}

	// 配列 - ソート
	qsort(sz1Wgt, siWCnt, sizeof(Wgt), fSortFnc);

	// 回答
	strcpy(lc1Out, "!");
	for (i = 0; i < siWCnt; i++) {
		sprintf(lc1Buf, " %d", sz1Wgt[i].miNo);
		strcat(lc1Out, lc1Buf);
	}
	strcat(lc1Out, "\n");
	fOut(lc1Out);

	return 0;
}

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

	// データ - 初期化
	memset(sz1Wgt, 0, sizeof(sz1Wgt));							// 重り

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