結果

問題 No.282 おもりと天秤(2)
ユーザー 紙ぺーぱー紙ぺーぱー
提出日時 2015-08-23 15:19:28
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,221 bytes
コンパイル時間 951 ms
コンパイル使用メモリ 112,648 KB
実行使用メモリ 52,136 KB
平均クエリ数 436.33
最終ジャッジ日時 2024-07-16 05:42:34
合計ジャッジ時間 39,554 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
41,000 KB
testcase_01 AC 62 ms
40,616 KB
testcase_02 AC 49 ms
40,672 KB
testcase_03 WA -
testcase_04 AC 47 ms
41,164 KB
testcase_05 WA -
testcase_06 AC 67 ms
43,220 KB
testcase_07 AC 47 ms
40,996 KB
testcase_08 AC 68 ms
43,096 KB
testcase_09 AC 45 ms
40,332 KB
testcase_10 AC 900 ms
47,752 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2,674 ms
47,640 KB
testcase_15 AC 3,217 ms
45,712 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 3,426 ms
47,904 KB
testcase_22 WA -
testcase_23 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using static System.Linq.Enumerable;
using static System.Math;
namespace Program
{

    public class Solver
    {
        /// <summary>
        ///parallel tree selection sort
        /// </summary>
        public void Solve()
        {
            var n = int.Parse(Console.ReadLine());
            var pos = new int[n + 1];
            var m = 1;
            while (m < n) m <<= 1;
            var a = new int?[m << 1];
            for (int i = 0; i < n; i++)
            {
                a[i + m] = i + 1;
                pos[i + 1] = i + m;
            }
            var ans = new List<int>();
            while (ans.Count < n)
            {
                var q = new int[2 * n];
                var p = 0;
                for (int i = 1; i < m; i++)
                {
                    if (a[i] != null)
                    {
                        if (i == 1)
                        {
                            ans.Add(a[i].Value);
                            pos[a[i].Value] = -1;
                            a[i] = null;
                        }
                        continue;
                    }
                    var l = i * 2;
                    var r = i * 2 + 1;
                    if (a[l] == null && a[r] == null)
                        continue;
                    else if (a[r] == null) { a[i] = a[l]; a[l] = null; pos[a[i].Value] = i; }
                    else if (a[l] == null) { a[i] = a[r]; a[r] = null; pos[a[i].Value] = i; }
                    else { q[p++] = a[l].Value; q[p++] = a[r].Value; }
                }
                if (p == 0) continue;
                Console.WriteLine("? {0}", q.AsJoinedString());
                var res = Console.ReadLine().Split();
                for (int i = 0; i < p; i += 2)
                {
                    if (res[i / 2] == "<")
                    {
                        var l = pos[q[i]];
                        a[l / 2] = a[l];
                        pos[q[i]] /= 2;
                        a[l] = null;
                    }
                    else
                    {
                        var r = pos[q[i + 1]];
                        a[r / 2] = a[r];
                        pos[q[i + 1]] /= 2;
                        a[r] = null;
                    }
                }
                //Debug.WriteLine(a.Select(x => x ?? -1).AsJoinedString());
            }
            Console.WriteLine("! {0}", ans.AsJoinedString());
        }

        static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }

    }

}
#region main
static class Ex
{
    static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
    static public void Main()
    {
        var solver = new Program.Solver();
        solver.Solve();
    }
}
#endregion
0