結果
| 問題 |
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.
ソースコード
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;
}
}
}
}