#694147 (C#) No.1698 Face to Face

提出ソース

結果

問題	No.1698 Face to Face
ユーザー	eSeF
提出日時	2021-08-29 17:55:30
言語	C# (.NET 8.0.203)
結果	RE
実行時間	-
コード長	13,245 bytes
コンパイル時間	8,376 ms
コンパイル使用メモリ	144,204 KB
実行使用メモリ	201,040 KB
最終ジャッジ日時	2023-09-26 15:46:10
合計ジャッジ時間	43,403 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	64 ms 30,676 KB
testcase_01	AC	63 ms 30,704 KB
testcase_02	AC	66 ms 32,656 KB
testcase_03	AC	407 ms 69,496 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	66 ms 30,744 KB
testcase_14	AC	67 ms 32,788 KB
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	AC	308 ms 50,292 KB
testcase_22	AC	239 ms 48,008 KB
testcase_23	AC	105 ms 38,300 KB
testcase_24	AC	348 ms 56,936 KB
testcase_25	RE	-
testcase_26	AC	99 ms 35,180 KB
testcase_27	AC	184 ms 44,240 KB
testcase_28	AC	194 ms 44,952 KB
testcase_29	AC	153 ms 46,792 KB
testcase_30	AC	405 ms 52,416 KB
testcase_31	AC	302 ms 54,036 KB
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	AC	70 ms 30,668 KB
testcase_36	AC	67 ms 30,884 KB
testcase_37	AC	66 ms 30,780 KB
testcase_38	AC	67 ms 30,656 KB
testcase_39	AC	67 ms 30,732 KB
testcase_40	AC	66 ms 30,780 KB
testcase_41	AC	66 ms 32,988 KB
testcase_42	AC	66 ms 30,776 KB
testcase_43	AC	67 ms 31,100 KB
testcase_44	AC	67 ms 30,788 KB
testcase_45	RE	-
testcase_46	WA	-
testcase_47	RE	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

  Determining projects to restore...
  Restored /home/judge/data/code/main.csproj (in 126 ms).
.NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f
Copyright (C) Microsoft Corporation.All rights reserved.

  プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください
  main -> /home/judge/data/code/bin/Release/net6.0/main.dll
  main -> /home/judge/data/code/bin/Release/net6.0/publish/

ソースコード

raw source code

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Numerics;
using System.Threading;
using System.Runtime.InteropServices;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using static System.Math;
using static System.Array;
using static AtCoder.Cout;
using static AtCoder.Tool;
namespace AtCoder
{
    class AC
    {
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 3;
        static readonly int[] dI = { 0, 1, 0, -1, 1, -1, -1, 1 };
        static readonly int[] dJ = { 1, 0, -1, 0, 1, 1, -1, -1 };
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw);

            /*var th = new Thread(Run, 1 << 26);
            th.Start();
            th.Join();*/

            Run();
            Console.Out.Flush();
        }
        static void Run()
        {
            int Testcase = 1;
            //Testcase = Cin.Int;
            for (var testcase_id = 0; testcase_id < Testcase; testcase_id++)
            {
                Solve(testcase_id);
            }
        }
        static void Solve(int testcase_id)
        {
            int N = Cin.Int;
            var A = Cin.ReadSplitInt;
            var B = Cin.ReadSplitInt;
            var Z = Cin.ReadSplitInt;
            var ida = new int[N];
            var idb = new int[N];
            for(var i = 0; i < N; i++)
            {
                A[i]--;B[i]--;
                Z[i]--;
                ida[A[i]] = i;
                idb[B[i]] = i;
            }

            //並列二分探索

            var pos_left = new int[N];
            var l = new int[N];
            var r = new int[N];
            for(var i = 0; i < N; i++)
            {
                l[i] = -1;r[i] = N;
            }
            var mid = new Queue<int>[N];
            for (var i = 0; i < N; i++) mid[i] = new Queue<int>();

            for(var _ = 0; _ < 16; _++)
            {
                // mid[i] : k = i で判定を行うペア番号の集合
                for (var i = 0; i < N; i++)
                    if (r[i] - l[i] > 1) mid[(l[i] + r[i]) / 2].Enqueue(i);
                var ufa = new DSU_AB(N);
                var ufb = new DSU_AB(N);
                for (var k = 0; k < N; k++)
                {
                    int ia = ida[k], ib = idb[k];
                    if (0 < ia && A[ia - 1] <= k) ufa.Unite(ia - 1, ia);
                    if (ia + 1 < N && A[ia + 1] <= k) ufa.Unite(ia, ia + 1);
                    if (0 < ib && B[ib - 1] <= k) ufb.Unite(ib - 1, ib);
                    if (ib + 1 < N && B[ib + 1] <= k) ufb.Unite(ib, ib + 1);

                    while(mid[k].Any())
                    {
                        int j = mid[k].Dequeue();
                        //この k の値において (j, Z_j) を同じ位置に配置することはできるか？
                        if (ufa.Right(ida[j]) < ufb.Left(idb[Z[j]]) || ufb.Right(idb[Z[j]]) < ufa.Left(ida[j]))
                        {
                            l[j] = k;
                        }
                        else
                        {
                            r[j] = k;
                            pos_left[j] = Max(ufa.Left(ida[j]), ufb.Left(idb[Z[j]]));
                        }
                    }
                }
            }
            for (var i = 0; i < N; i++) mid[r[i]].Enqueue(i);

            //答えを求める

            var ufi = new DSU_Idx(N);
            var less_k = new int[N];
            for(var k = 0; k < N; k++)
            {
                int ia = ida[k], ib = idb[k];
                less_k[ia]++;less_k[ib]++;
                if (less_k[ia] == 2)
                {
                    if (0 < ia && less_k[ia - 1] == 2) ufi.Unite(ia - 1, ia);
                    if (ia + 1 < N && less_k[ia + 1] == 2) ufi.Unite(ia, ia + 1);
                }
                if (less_k[ib] == 2)
                {
                    if (0 < ib && less_k[ib - 1] == 2) ufi.Unite(ib - 1, ib);
                    if (ib + 1 < N && less_k[ib + 1] == 2) ufi.Unite(ib, ib + 1);
                }

                foreach(var i in mid[k])
                {
                    ufi.Add_Pair(pos_left[i]);
                }

                OutL(ufi.Score);
            }
        }
    }
    public class DSU_AB
    {
        private int n;
        private int[] par_size;
        private int[] left;
        private int[] right;
        // par_size[i] = sizeof(i) (par_size[i] <  0)
        //               parent(i) (par_size[i] >= 0)
        public DSU_AB(int size)
        {
            n = size;
            par_size = new int[n];
            left = new int[n];
            right = new int[n];
            for (var i = 0; i < n; i++)
            {
                par_size[i] = -1;
                left[i] = right[i] = i;
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Root(int v)
        {
            if (par_size[v] < 0) return v;
            while (par_size[par_size[v]] >= 0)
            {
                (v, par_size[v]) = (par_size[v], par_size[par_size[v]]);
            }
            return par_size[v];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int SizeOf(int v) => -par_size[Root(v)];

        public void Unite(int u, int v)
        {
            int ru = Root(u), rv = Root(v);
            if (ru == rv) return;
            if (par_size[ru] > par_size[rv])
            {
                par_size[rv] += par_size[ru];
                par_size[ru] = rv;

                left[rv] = Min(left[rv], left[ru]);
                right[rv] = Max(right[rv], right[ru]);
            }
            else
            {
                par_size[ru] += par_size[rv];
                par_size[rv] = ru;

                left[ru] = Min(left[ru], left[rv]);
                right[ru] = Max(right[ru], right[rv]);
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Same(int u, int v) => Root(u) == Root(v);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Left(int v) => left[Root(v)];
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Right(int v) => right[Root(v)];

    }
    public class DSU_Idx
    {
        private int n;
        private int[] par_size;
        private int[] num_pair;
        public int Score;
        // par_size[i] = sizeof(i) (par_size[i] <  0)
        //               parent(i) (par_size[i] >= 0)
        public DSU_Idx(int size)
        {
            n = size;
            par_size = new int[n];
            num_pair = new int[n];
            Score = 0;
            for (var i = 0; i < n; i++)
            {
                par_size[i] = -1;
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Root(int v)
        {
            if (par_size[v] < 0) return v;
            while (par_size[par_size[v]] >= 0)
            {
                (v, par_size[v]) = (par_size[v], par_size[par_size[v]]);
            }
            return par_size[v];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int SizeOf(int v) => -par_size[Root(v)];
        // unite, num_pair更新時にScoreを差分更新する
        public void Unite(int u, int v)
        {
            int ru = Root(u), rv = Root(v);
            if (ru == rv) return;

            Score -= (Sub_score(ru) + Sub_score(rv));

            if (par_size[ru] > par_size[rv])
            {
                par_size[rv] += par_size[ru];
                par_size[ru] = rv;

                num_pair[rv] += num_pair[ru];
                Score += Sub_score(rv);
            }
            else
            {
                par_size[ru] += par_size[rv];
                par_size[rv] = ru;

                num_pair[ru] += num_pair[rv];
                Score += Sub_score(ru);
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add_Pair(int v)
        {
            Score -= Sub_score(v);
            num_pair[Root(v)]++;
            Score += Sub_score(v);
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Sub_score(int v) => Min(-par_size[Root(v)], num_pair[Root(v)]);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Same(int u, int v) => Root(u) == Root(v);

    }
    static class Cin
    {
        public static string[] ReadSplit => Console.ReadLine().Split();
        public static int[] ReadSplitInt => ConvertAll(ReadSplit, int.Parse);
        public static long[] ReadSplitLong => ConvertAll(ReadSplit, long.Parse);
        public static double[] ReadSplit_Double => ConvertAll(ReadSplit, double.Parse);
        public static string Str => Console.ReadLine();
        public static int Int => int.Parse(Console.ReadLine());
        public static long Long => long.Parse(Console.ReadLine());
        public static double Double => double.Parse(Console.ReadLine());
        public static T Conv<T>(string input)
        {
            return (T)Convert.ChangeType(input, typeof(T));
        }
        public static void Scanf<T>(out T a) => a = Conv<T>(Console.ReadLine());
        public static void Scanf<T, U>(out T a, out U b)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); }
        public static void Scanf<T, U, V>(out T a, out U b, out V c)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); }
        public static void Scanf<T, U, V, W>(out T a, out U b, out V c, out W d)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); }
        public static void Scanf<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); e = Conv<X>(q[4]); }
    }
    static class Cout
    {
        public static void OutL(object s) => Console.WriteLine(s);
        public static void Out_Sep<T>(IEnumerable<T> s) => Console.WriteLine(string.Join(" ", s));
        public static void Out_Sep<T>(IEnumerable<T> s, string sep) => Console.WriteLine(string.Join($"{sep}", s));
        public static void Out_Sep(params object[] s) => Console.WriteLine(string.Join(" ", s));
        public static void Out_One(object s) => Console.Write($"{s} ");
        public static void Out_One(object s, string sep) => Console.Write($"{s}{sep}");
        public static void Endl() => Console.WriteLine();
    }
    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            array = ConvertAll(array, x => initialvalue);
        }
        static public void Swap<T>(ref T a, ref T b)
        {
            T keep = a;
            a = b;
            b = keep;
        }
        static public void Display<T>(T[,] array2d, int n, int m)
        {
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < m; j++)
                {
                    Console.Write($"{array2d[i, j]} ");
                }
                Console.WriteLine();
            }
        }
        static public int GcdI(int a, int b)
        {
            if (a == 0 || b == 0) return Max(a, b);
            return a % b == 0 ? b : GcdI(b, a % b);
        }
        static public long Gcd(long a, long b)
        {
            if (a == 0 || b == 0) return Max(a, b);
            return a % b == 0 ? b : Gcd(b, a % b);
        }
        static public long Lcm(long a, long b) => a / Gcd(a, b) * b;
        static public int LcmI(int a, int b) => (a == 0 || b == 0) ? Max(a, b) : a / GcdI(a, b) * b;
        static public long ExtGcd(long a, long b, ref long x, ref long y)
        {
            // ax + by = gcd(a,b) なる x,y を求める // return gcd(a,b)
            if (b == 0)
            {
                x = 1; y = 0;
                return a;
            }
            long d = ExtGcd(b, a % b, ref y, ref x);
            y -= a / b * x;
            return d;
        }
        static public long LPow(int a, int b) => (long)Pow(a, b);
        static public bool Bit(long x, int dig) => ((1L << dig) & x) != 0;
        static public int Sig(long a) => a == 0 ? 0 : (int)(a / Abs(a));
        static public long F_mp(long x, long n, long mod) => n == 0 ? (1 % mod) : (n % 2 == 0 ? F_mp((x * x) % mod, n >> 1, mod) : (x * F_mp(x, n - 1, mod)) % mod);
        static public long F_inv(long x, long mod) => F_mp(x, mod - 2, mod);
        static public decimal DSqrt(decimal x, decimal epsilon = 0.0M)
        {
            if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");

            decimal current = (decimal)Math.Sqrt((double)x), previous;
            do
            {
                previous = current;
                if (previous == 0.0M) return 0;
                current = (previous + x / previous) / 2;
            }
            while (Math.Abs(previous - current) > epsilon);
            return current;
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード