結果
問題 | No.2496 LCM between Permutations |
ユーザー |
|
提出日時 | 2023-10-08 22:31:42 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 5,855 bytes |
コンパイル時間 | 1,045 ms |
コンパイル使用メモリ | 113,640 KB |
実行使用メモリ | 43,004 KB |
平均クエリ数 | 953.79 |
最終ジャッジ日時 | 2024-07-26 18:13:44 |
合計ジャッジ時間 | 4,962 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();public static void Main(){Solve();}static void Solve(){var n = NN;if (n == 1){Solve1();return;}if (n == 2){Solve2();return;}var llist = new int[n];var plist = new Dictionary<int, int>[n];for (var i = 0; i < n; ++i){llist[i] = Ask(i, i);plist[i] = PDiv(llist[i]);}var a = new int[n];var b = new int[n];for (var i = 0; i < n; ++i){var p = 0;foreach (var kv in plist[i]){if (kv.Key > n / 2){p = kv.Key;break;}}if (p == 0) continue;for (var j = 0; j < n; ++j){if (!plist[j].ContainsKey(p)){var lcm = Ask(i, j);if (lcm % p != 0) rev = true;a[i] = p;var bpos = 0;for (var k = 0; k < n; ++k){if (i == k){b[k] = llist[i] == p ? llist[k] : (llist[i] / p);}else{var l = Ask(i, k);if (l == p) bpos = k;b[k] = l == p ? l : (l / p);}}// b[bpos] = 1 or pfor (var k = 0; k < n; ++k){if (bpos == k){// a[k] = (llist[k] <= p) ? llist[k] : (llist[k] / p);a[k] = llist[k];}else{var l = Ask(k, bpos);if (l % p != 0) b[bpos] = 1;a[k] = l;}}// WriteLine(string.Join(" ", a));for (var k = 0; k < n; ++k) if (i != k){a[k] /= b[bpos];}for (var k = 0; k < n; ++k){if (i != k && a[k] == p){a[k] = 1;}if (a[k] == 1){for (var m = 0; m < n; ++m) if (m != bpos && b[m] == p){var l = Ask(k, m);if (l == 1) b[m] = 1;else b[bpos] = 1;break;}break;}}break;}}break;}Ans(a, b);// WriteLine($"asks: {asks}");// Check(a, b);}static void Solve1(){WriteLine("! 1 1");}static void Solve2(){var a = new int[] { 2, 2 };var b = new int[] { 2, 2 };for (var i = 0; i < 2; ++i) for (var j = 0; j < 2; ++j){if (Ask(i, j) == 1){a[i] = 1;b[j] = 1;}}Ans(a, b);}static bool rev;static int asks = 0;static int Ask(int i, int j){// return a[i] * b[j] / GCD(a[i], b[j]);if (rev) WriteLine($"? {j + 1} {i + 1}");else WriteLine($"? {i + 1} {j + 1}");++asks;return NN;}static bool Ans(int[] a, int[] b){if (rev) WriteLine($"! {string.Join(" ", b)} {string.Join(" ", a)}");else WriteLine($"! {string.Join(" ", a)} {string.Join(" ", b)}");return true;}static Dictionary<int, int> PDiv(int n){var dic = new Dictionary<int, int>();var tmp = n;while (tmp % 2 == 0){tmp /= 2;if (dic.ContainsKey(2)) ++dic[2];else dic.Add(2, 1);}for (var p = 3; p * p <= n; p += 2){while (tmp % p == 0){tmp /= p;if (dic.ContainsKey(p)) ++dic[p];else dic.Add(p, 1);}if (tmp == 1) break;}if (tmp > 1) dic.Add(tmp, 1);return dic;}static void DebugDic<T, U>(Dictionary<T, U> dic){Console.WriteLine("Dic:");foreach (var kv in dic) Console.WriteLine(" {0} = {1}", kv.Key, kv.Value);}static void Check(int[] a, int[] b){var la = a.ToList();la.Sort();var lb = b.ToList();lb.Sort();for (var i = 0; i + 1 < la.Count; ++i){if (la[i] == 0 || lb[i] == 0){WriteLine("zero found");return;}if (la[i] == la[i + 1] || lb[i] == lb[i + 1]){WriteLine("Duplicate");return;}}}}