結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
ユーザー kakel-sankakel-san
提出日時 2024-08-08 23:19:09
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 960 ms / 2,000 ms
コード長 5,064 bytes
コンパイル時間 8,035 ms
コンパイル使用メモリ 169,896 KB
実行使用メモリ 188,840 KB
最終ジャッジ日時 2024-08-08 23:19:49
合計ジャッジ時間 36,583 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 74
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (98 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
プレゼンテーションモードにする

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (k, l, m, n, s) = (c[0], c[1], c[2], c[3], c[4]);
var a = NList;
var b = NList;
c = NList;
var d = NList;
var q = Qua(k, l, m, n, s, a, b, c, d);
WriteLine(q.t);
WriteLine(q.ans);
}
static (long t, string ans) Qua(long k, long l, long m, long n, long s, long[] a, long[] b, long[] c, long[] d)
{
var firstp = new List<(long a, long b, long x)>();
var firstn = new List<(long a, long b, long x)>();
var firstz = new List<(long a, long b)>();
for (var i = 0; i < k; ++i) for (var j = 0; j < l; ++j)
{
if (a[i] * b[j] > 0) firstp.Add((a[i], b[j], a[i] * b[j]));
else if (a[i] * b[j] < 0) firstn.Add((a[i], b[j], a[i] * b[j]));
else firstz.Add((a[i], b[j]));
}
var secondp = new List<(long c, long d, long x)>();
var secondn = new List<(long c, long d, long x)>();
var secondz = new List<(long c, long d)>();
for (var i = 0; i < m; ++i) for (var j = 0; j < n; ++j)
{
if (c[i] * d[j] > 0) secondp.Add((c[i], d[j], c[i] * d[j]));
else if (c[i] * d[j] < 0) secondn.Add((c[i], d[j], c[i] * d[j]));
else secondz.Add((c[i], d[j]));
}
firstp.Sort((l, r) => l.x.CompareTo(r.x));
firstn.Sort((l, r) => r.x.CompareTo(l.x));
secondp.Sort((l, r) => l.x.CompareTo(r.x));
secondn.Sort((l, r) => r.x.CompareTo(l.x));
var ok = -1_000_000_000_000_000_000;
var ng = 1_000_000_000_000_000_000;
var ans = "";
while (ng - ok > 1)
{
var sub = "";
var mid = (ok + ng) / 2;
// TABCD S-1
var count = 0L;
if (mid < 0)
{
var cur = secondn.Count - 1;
for (var i = 0; i < firstp.Count; ++i)
{
while (cur >= 0 && firstp[i].x * secondn[cur].x < mid) --cur;
count += secondn.Count - 1 - cur;
if (cur >= 0 && firstp[i].x * secondn[cur].x == mid)
{
sub = $"{firstp[i].a} {firstp[i].b} {secondn[cur].c} {secondn[cur].d}";
}
}
cur = secondp.Count - 1;
for (var i = 0; i < firstn.Count; ++i)
{
while (cur >= 0 && firstn[i].x * secondp[cur].x < mid) --cur;
count += secondp.Count - 1 - cur;
if (cur >= 0 && firstn[i].x * secondp[cur].x == mid)
{
sub = $"{firstn[i].a} {firstn[i].b} {secondp[cur].c} {secondp[cur].d}";
}
}
}
else if (mid > 0)
{
count += firstp.Count * ((long)secondn.Count + secondz.Count) +
firstn.Count * ((long)secondp.Count + secondz.Count) +
firstz.Count * ((long)secondp.Count + secondn.Count + secondz.Count);
var cur = 0;
for (var i = firstp.Count - 1; i >= 0; --i)
{
while (cur < secondp.Count && firstp[i].x * secondp[cur].x < mid) ++cur;
count += cur;
if (cur < secondp.Count && firstp[i].x * secondp[cur].x == mid)
{
sub = $"{firstp[i].a} {firstp[i].b} {secondp[cur].c} {secondp[cur].d}";
}
}
cur = 0;
for (var i = firstn.Count - 1; i >= 0; --i)
{
while (cur < secondn.Count && firstn[i].x * secondn[cur].x < mid) ++cur;
count += cur;
if (cur < secondn.Count && firstn[i].x * secondn[cur].x == mid)
{
sub = $"{firstn[i].a} {firstn[i].b} {secondn[cur].c} {secondn[cur].d}";
}
}
}
else
{
count += (long)firstp.Count * secondn.Count + (long)firstn.Count * secondp.Count;
if (firstz.Count > 0) sub = $"{firstz[0].a} {firstz[0].b} {c[0]} {d[0]}";
else if (secondz.Count > 0) sub = $"{a[0]} {b[0]} {secondz[0].c} {secondz[0].d}";
}
if (count <= s - 1)
{
ok = mid;
ans = sub;
}
else ng = mid;
}
return (ok, ans);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0