結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
|
提出日時 | 2024-08-08 22:28:37 |
言語 | C# (.NET 8.0.404) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,107 bytes |
コンパイル時間 | 16,992 ms |
コンパイル使用メモリ | 166,160 KB |
実行使用メモリ | 189,052 KB |
最終ジャッジ日時 | 2024-08-08 22:29:25 |
合計ジャッジ時間 | 42,339 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 WA * 52 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (122 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 firstp = new List<(long a, long b, long x)>(); var firstn = new List<(long a, long b, long x)>(); 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 firstn.Add((a[i], b[j], a[i] * b[j])); } var secondp = new List<(long c, long d, long x)>(); var secondn = new List<(long c, long d, long x)>(); 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 secondn.Add((c[i], d[j], 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 = -810_000_000_000_000_000; var ng = 810_000_000_000_000_001; 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 = 0; for (var i = firstp.Count - 1; i >= 0; --i) { while (cur < secondn.Count && firstp[i].x * secondn[cur].x >= mid) ++cur; count += secondn.Count - cur; if (cur < secondn.Count && firstp[i].x * secondn[cur].x == mid) { sub = $"{firstp[i].a} {firstp[i].b} {secondn[cur].c} {secondn[cur].d}"; } } cur = 0; for (var i = firstn.Count - 1; i >= 0; --i) { while (cur < secondp.Count && firstn[i].x * secondp[cur].x >= mid) ++cur; count += secondp.Count - cur; if (cur < secondp.Count && firstn[i].x * secondp[cur].x == mid) { sub = $"{firstn[i].a} {firstn[i].b} {secondp[cur].c} {secondp[cur].d}"; } } } else { count += (long)firstp.Count * secondn.Count + (long)firstn.Count * secondp.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}"; } } 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}"; } } } if (count <= s - 1) { ok = mid; ans = sub; } else ng = mid; } WriteLine(ok); WriteLine(ans); } }