結果

問題 No.2453 Seat Allocation
ユーザー k82bk82b
提出日時 2023-09-01 22:43:35
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 


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;}
0