#910046 (D) No.2453 Seat Allocation

• 問題: No.2453 Seat Allocation
• ユーザー: k82b
• 提出日時: 2023-09-01 22:43:35
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 124 ms / 2,000 ms
• コード長: 1,475 bytes
• コンパイル時間: 4,434 ms
• コンパイル使用メモリ: 199,392 KB
• 実行使用メモリ: 12,032 KB
• 最終ジャッジ日時: 2024-06-25 09:29:56
• 合計ジャッジ時間: 6,342 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	108 ms; 12,032 KB
testcase_06	AC	62 ms; 5,668 KB
testcase_07	AC	19 ms; 6,784 KB
testcase_08	AC	10 ms; 5,376 KB
testcase_09	AC	124 ms; 10,516 KB
testcase_10	AC	122 ms; 10,408 KB
testcase_11	AC	122 ms; 10,500 KB
testcase_12	AC	63 ms; 5,644 KB
testcase_13	AC	70 ms; 5,796 KB
testcase_14	AC	58 ms; 5,644 KB
testcase_15	AC	80 ms; 5,684 KB
testcase_16	AC	67 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	89 ms; 7,056 KB
testcase_19	AC	101 ms; 8,912 KB
testcase_20	AC	41 ms; 5,656 KB
testcase_21	AC	61 ms; 5,376 KB
testcase_22	AC	87 ms; 6,272 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	1 ms; 5,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;}