結果

問題 No.2496 LCM between Permutations
ユーザー kakel-sankakel-san
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
40,976 KB
testcase_01 AC 42 ms
40,196 KB
testcase_02 AC 42 ms
40,456 KB
testcase_03 AC 42 ms
38,672 KB
testcase_04 AC 44 ms
40,808 KB
testcase_05 AC 48 ms
40,712 KB
testcase_06 AC 44 ms
40,472 KB
testcase_07 AC 48 ms
38,804 KB
testcase_08 AC 45 ms
41,096 KB
testcase_09 AC 44 ms
40,836 KB
testcase_10 AC 44 ms
40,716 KB
testcase_11 AC 46 ms
42,468 KB
testcase_12 AC 45 ms
42,472 KB
testcase_13 AC 46 ms
40,964 KB
testcase_14 AC 46 ms
40,580 KB
testcase_15 AC 53 ms
41,104 KB
testcase_16 AC 53 ms
42,624 KB
testcase_17 AC 60 ms
42,856 KB
testcase_18 AC 130 ms
42,876 KB
testcase_19 AC 105 ms
40,720 KB
testcase_20 AC 135 ms
43,004 KB
testcase_21 AC 110 ms
42,376 KB
testcase_22 AC 105 ms
42,764 KB
testcase_23 AC 143 ms
40,452 KB
testcase_24 AC 122 ms
42,508 KB
testcase_25 AC 143 ms
42,628 KB
testcase_26 AC 146 ms
42,636 KB
testcase_27 AC 143 ms
38,792 KB
testcase_28 AC 150 ms
40,828 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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 p
                    for (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;
            }
        }
    }
}
0