結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー |
|
提出日時 | 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/
ソースコード
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;// Tよりも小さいABCDの数が 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);}}