#910046 (D) No.2453 Seat Allocation

• 問題: No.2453 Seat Allocation
• ユーザー: k82b
• 提出日時: 2023-09-01 22:43:35
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 128 ms / 2,000 ms
• コード長: 1,475 bytes
• コンパイル時間: 4,541 ms
• コンパイル使用メモリ: 187,980 KB
• 実行使用メモリ: 13,360 KB
• 最終ジャッジ日時: 2023-09-07 15:36:46
• 合計ジャッジ時間: 6,042 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,352 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	110 ms; 13,360 KB
testcase_06	AC	66 ms; 7,432 KB
testcase_07	AC	21 ms; 8,916 KB
testcase_08	AC	11 ms; 4,376 KB
testcase_09	AC	128 ms; 11,564 KB
testcase_10	AC	125 ms; 11,424 KB
testcase_11	AC	125 ms; 11,352 KB
testcase_12	AC	66 ms; 6,796 KB
testcase_13	AC	74 ms; 7,388 KB
testcase_14	AC	61 ms; 7,700 KB
testcase_15	AC	84 ms; 7,216 KB
testcase_16	AC	69 ms; 6,916 KB
testcase_17	AC	2 ms; 4,380 KB
testcase_18	AC	92 ms; 7,952 KB
testcase_19	AC	105 ms; 10,976 KB
testcase_20	AC	42 ms; 7,364 KB
testcase_21	AC	63 ms; 6,924 KB
testcase_22	AC	90 ms; 7,144 KB
testcase_23	AC	1 ms; 4,376 KB
testcase_24	AC	2 ms; 4,376 KB

ソースコード

void main()
{
	alias Entry=Tuple!(int,"a",int,"b",int,"I",int,"id");
	const N=readInt;
	const M=readInt;
	auto A=new int[N];
	auto B=new int[M];
	foreach(i;0..N)
	{
		A[i]=readInt;
	}
	foreach(i;0..M)
	{
		B[i]=readInt;
	}

	bool f(Entry x,Entry y)
	{
		long xa=cast(long)x.a;
		long ya=cast(long)y.a;
		long xb=cast(long)x.b;
		long yb=cast(long)y.b;
		if(xa*yb==ya*xb)
		{
			return x.I>y.I;
		}
		return xa*yb<ya*xb;
	}
	auto Q=new BinaryHeap!(Array!Entry,f);
	foreach(i;0..N)
	{
		Q.insert(Entry(A[i],B[0],i,1));
	}
	foreach(i;0..M)
	{
		Entry now=Q.front;
		Q.popFront;
		writeln(now.I+1);
		if(i==M-1)break;
		Q.insert(Entry(now.a,B[now.id],now.I,now.id+1));
	}
}

import std;

string[]__READ;
string readString(){while(__READ.empty()){__READ=readln.chomp.split;}auto ret=__READ.front;__READ.popFront;return ret;}
int readInt(){return readString.to!int;}
uint readuInt(){return readString.to!uint;}
long readLong(){return readString.to!long;}
ulong readuLong(){return readString.to!ulong;}
double readDouble(){return readString.to!double;}
real readReal(){return readString.to!real;}

bool chmin(T)(ref T A,T B){if(A>B){A=B;return true;}else{return false;}}
bool chmax(T)(ref T A,T B){if(A<B){A=B;return true;}else{return false;}}

int lowerBound(T)(T[]A,T x){int L=-1,R=cast(int)A.length;while(R-L>1){int mid=(L+R)/2;(A[mid]<x?L:R)=mid;}return R;}
int upperBound(T)(T[]A,T x){int L=-1,R=cast(int)A.length;while(R-L>1){int mid=(L+R)/2;(A[mid]<=x?L:R)=mid;}return R;}