結果
問題 |
No.3088 XOR = SUM
|
ユーザー |
|
提出日時 | 2025-04-04 22:23:59 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 3,694 bytes |
コンパイル時間 | 15,127 ms |
コンパイル使用メモリ | 172,992 KB |
実行使用メモリ | 195,560 KB |
最終ジャッジ日時 | 2025-04-04 22:25:05 |
合計ジャッジ時間 | 30,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (112 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable using System.Numerics; void Run() { var t = Int(); var ans = new string[t]; for (var i = 0; i < t; i++) { var n = ulong.Parse(String()); if (n == 0) { ans[i] = "0 0"; continue; } var lz = BitOperations.LeadingZeroCount(n); var x = 1UL << (63 - lz); var y = n - x; if (x > 1) { var x2 = x >> 1; var y2 = x2 - 1; if ((UInt128)x * y < (UInt128)x2 * y2) { (x, y) = (x2, y2); } } ans[i] = x + " " + y; } Out(ans); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); class AtCoderIO { public required StandardIOBackend Backend { get; init; } Memory<string> _input = Array.Empty<string>(); int _iter = 0; public string Next() { while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0); return _input.Span[_iter++]; } public void Out(object? x, string? separator = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast<object>(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } Backend.WriteLine(x); } } class StandardIOBackend { readonly StreamReader _sr = new(Console.OpenStandardInput()); readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; public string ReadLine() => _sr.ReadLine()!; public void WriteLine(object? value) => _sw.WriteLine(value); public void Flush() => _sw.Flush(); } #endregion static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } class UnionFind { (int parent, int edgeCount)[] Verticals { get; set; } bool EnabledUndo { get; init; } Stack<(int v, (int parent, int edges))> Histories { get; init; } public UnionFind(int verticals, bool enableUndo = false) { Verticals = new (int, int)[verticals]; for (int i = 0; i < verticals; i++) Verticals[i] = (-1, 0); Histories = new(); EnabledUndo = enableUndo; } public int Union(int x, int y) { (x, y) = (Find(x), Find(y)); var (sx, sy) = (Size(x), Size(y)); if (sx < sy) (x, y, sy) = (y, x, sx); var (nx, ny) = (Verticals[x], Verticals[y]); Histories.Push((x, nx)); Histories.Push((y, ny)); if (x == y) nx.edgeCount += 1; else { ny.parent = x; nx.parent -= sy; nx.edgeCount += ny.edgeCount + 1; } (Verticals[y], Verticals[x]) = (ny, nx); return x; } public int Find(int x) { var pid = Verticals[x].parent; if (pid < 0) return x; var aid = Find(pid); if (!EnabledUndo) Verticals[x].parent = aid; return aid; } public int Size(int x) => -Verticals[Find(x)].parent; public int EdgeCount(int x) => Verticals[Find(x)].edgeCount; public bool Undo() { if (!EnabledUndo || Histories.Count == 0) return false; for (var i = 0; i < 2; i++) { var (v, h) = Histories.Pop(); Verticals[v] = h; } return true; } }