結果
| 問題 | No.2496 LCM between Permutations |
| ユーザー |
👑  kakel-san
|
| 提出日時 | 2023-10-08 22:31:42 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 225 ms / 2,000 ms |
| コード長 | 5,855 bytes |
| コンパイル時間 | 1,021 ms |
| コンパイル使用メモリ | 66,488 KB |
| 実行使用メモリ | 38,708 KB |
| 平均クエリ数 | 953.79 |
| 最終ジャッジ日時 | 2023-10-08 22:31:49 |
| 合計ジャッジ時間 | 6,782 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 86 ms
38,332 KB |
| testcase_01 | AC | 75 ms
36,652 KB |
| testcase_02 | AC | 82 ms
36,984 KB |
| testcase_03 | AC | 83 ms
38,708 KB |
| testcase_04 | AC | 84 ms
37,176 KB |
| testcase_05 | AC | 84 ms
34,280 KB |
| testcase_06 | AC | 86 ms
38,608 KB |
| testcase_07 | AC | 85 ms
36,860 KB |
| testcase_08 | AC | 94 ms
36,572 KB |
| testcase_09 | AC | 87 ms
38,516 KB |
| testcase_10 | AC | 86 ms
38,408 KB |
| testcase_11 | AC | 86 ms
36,152 KB |
| testcase_12 | AC | 85 ms
36,592 KB |
| testcase_13 | AC | 86 ms
36,744 KB |
| testcase_14 | AC | 87 ms
36,488 KB |
| testcase_15 | AC | 93 ms
36,380 KB |
| testcase_16 | AC | 93 ms
36,740 KB |
| testcase_17 | AC | 95 ms
38,212 KB |
| testcase_18 | AC | 163 ms
36,424 KB |
| testcase_19 | AC | 137 ms
36,296 KB |
| testcase_20 | AC | 171 ms
36,992 KB |
| testcase_21 | AC | 158 ms
38,304 KB |
| testcase_22 | AC | 157 ms
37,212 KB |
| testcase_23 | AC | 206 ms
37,092 KB |
| testcase_24 | AC | 168 ms
37,132 KB |
| testcase_25 | AC | 193 ms
34,800 KB |
| testcase_26 | AC | 195 ms
36,364 KB |
| testcase_27 | AC | 195 ms
37,192 KB |
| testcase_28 | AC | 225 ms
36,436 KB |
ソースコード
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;
}
}
}
}