Submission #20504139


Source Code Expand

Copy
using AtCoder;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using static System.Math;
using static System.Numerics.BitOperations;
using static Kzrnm.Competitive.BitOperationsEx;
using static Kzrnm.Competitive.Global;
using static Kzrnm.Competitive.MathLibEx;
using static Kzrnm.Competitive.__BinarySearchEx;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod1000000007>;
using static Program;

partial class Program
{
    partial void WriteBool(bool b) => cw.WriteLine(b ? "Yes" : "No");
    bool __ManyTestCases() => false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        static int CrossSign(long x1, long y1, long x2, long y2) => Sign(x1 * y2 - y1 * x2);
        int N = cr;
        var points = cr.Repeat(N).Select(cr => new PointInt(cr, cr));

        var pts = new (int x, int y, int ix)[points.Length];
        for (int i = 0; i < points.Length; i++)
            pts[i] = (points[i].x, points[i].y, i);
        Array.Sort(pts);

        var upper = new SList<(int x, int y, int ix)> { pts[0], pts[1] };
        var lower = new SList<(int x, int y, int ix)> { pts[0], pts[1] };
        for (int i = 2; i < pts.Length; i++)
        {
            while (upper.Count > 1
                && CrossSign(upper[^1].x - upper[^2].x, upper[^1].y - upper[^2].y, pts[i].x - upper[^2].x, pts[i].y - upper[^2].y) > 0)
            {
                upper.RemoveLast();
            }
            upper.Add(pts[i]);
            while (lower.Count > 1
                && CrossSign(lower[^1].x - lower[^2].x, lower[^1].y - lower[^2].y, pts[i].x - lower[^2].x, pts[i].y - lower[^2].y) < 0)
            {
                lower.RemoveLast();
            }
            lower.Add(pts[i]);
        }

        var res = new SList<int>(N);
        var used = new bool[N];
        foreach (var (_, _, ix) in upper)
        {
            used[ix] = true;
            res.Add(ix + 1);
        }
        res.Reverse();

        foreach (var (_, _, ix) in pts)
            if (!used[ix])
                res.Add(ix + 1);

        cw.WriteLines(res.AsSpan());

        return null;
    }
}

Submission Info

Submission Time
Task B - Jumps
User naminodarie
Language C# (.NET Core 3.1.201)
Score 0
Code Size 2342 Byte
Status IE