結果

問題 No.2496 LCM between Permutations
ユーザー kakel-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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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.

ソースコード

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;
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0