paizaオンラインハッカソンVol.1 https://paiza.jp/poh/ec-campaign のC#版 結果: http://paiza.jp/poh/ec-campaign/result/f29e7304681bf8998f4efbd1bed78c4e

paiza.cs

using System;
using System.Runtime.InteropServices;


public static class Program
{
    [DllImport("libc")]
    static extern void printf(string format, int value);

    [DllImport("libc")]
    static extern int scanf(string format, out int value1, out int value2);

    [DllImport("libc")]
    private static extern int fread(IntPtr buf, int size, int n, IntPtr fp); //Assume 32bit machine

    [DllImport("MonoPosixHelper", EntryPoint = "Mono_Posix_Stdlib_stdin")]
    private static extern IntPtr GetStandardInput();

    private const int MAX_PRODUCT_PRICE = 200000;
    private const int TEMP_BUFFER_LENGTH = 1024 * 100; //100KB

    static void Main()
    {
        //Load first line
        int productCount;
        int campaignDays;
        scanf("%d %d\n", out productCount, out campaignDays);

        //Allocate memory heap
        var buffer = new int[productCount + campaignDays];
        var countTable = new int[MAX_PRODUCT_PRICE + 1];
        var tempBuffer = new byte[TEMP_BUFFER_LENGTH];

        //Load data to buffer
        LoadData(buffer, tempBuffer);

        //Sort data (remove duplicate values)
        int count = buffer.SortByBucketSort(productCount, countTable);

        //Calculate best prices
        for (var i = 0; i < campaignDays; ++i)
        {
            int dayCampaignPrice = buffer[productCount + i];
            int bestPrice = FindBestPrice(dayCampaignPrice, buffer, count, countTable);
            printf("%d\n", bestPrice);
        }
    }

    private static void LoadData(int[] buffer, byte[] tempBuffer)
    {
        //GCHandle.Alloc(tempBuffer,GCHandleType.Pinned); 
        var intPtr = Marshal.UnsafeAddrOfPinnedArrayElement(tempBuffer, 0);

        var stdin = GetStandardInput(); //Get stdin pointer

        int n = 0; //buffer index
        int value = 0;
        int bytes;

        //Load data to temp buffer 
        while (0 < (bytes = fread(intPtr, sizeof(byte), TEMP_BUFFER_LENGTH, stdin)))
        {
            //Read input and convert chars to number
            for (int i = 0; i < bytes; ++i)
            {
                var num = tempBuffer[i];
                switch (num)
                {
                    case (byte)'\n':
                        buffer[n++] = value;
                        value = 0;
                        break;
                    default:
                        value = 10 * value + (num - '0');
                        break;
                }
            }
        }

        //Last input don't contain LineSeparator char
        if (n < buffer.Length)
            buffer[n] = value;
    }

    private static int FindBestPrice(int dayCampaignPrice, int[] productPrices, int productCount, int[] countTable)
    {
        int head = 0;
        int tail = productPrices.FindIndex(productCount, dayCampaignPrice - productPrices[0]);

        int resultCandidate = 0;
        while (head < tail)
        {
            var sum = productPrices[head] + productPrices[tail];
            if (sum > dayCampaignPrice)
            {
                --tail;
            }
            else if (sum < dayCampaignPrice)
            {
                ++head;
                resultCandidate = Math.Max(resultCandidate, sum);
            }
            else
            {
                return dayCampaignPrice;
            }
        }

        if (countTable[productPrices[head]] > 1)
            resultCandidate = Math.Max(resultCandidate, productPrices[head] * 2);

        return resultCandidate;
    }

    public static int SortByBucketSort(this int[] buffer, int count, int[] countTable)
    {
        for (int i = 0; i < count; ++i)
        {
            var v = buffer[i];
            ++countTable[v];
            //maxPrice = Math.Max(maxPrice, v);
        }

        //Get max campaign price(better than using max product price?)
        int maxCampaignPrice = 0;
        for (int i = count; i < buffer.Length; ++i)
        {
            maxCampaignPrice = Math.Max(maxCampaignPrice, buffer[i]);
        }

        int n = 0;
        for (int i = 10; i <= maxCampaignPrice; ++i)
        {
            if (countTable[i] > 0)
            {
                buffer[n++] = i;
            }
        }
        return n;
    }

    public static int FindIndex(this int[] productPrices, int productCount, int candidatePrice)
    {
        int left = 0;
        int right = productCount - 1;

        while (left <= right)
        {
            int index = left + ((right - left) >> 1);
            var value = productPrices[index];

            if (value < candidatePrice)
                left = index + 1;
            else if (value > candidatePrice)
                right = index - 1;
            else
                return index;
        }
        return Math.Min(productCount - 1, right);
    }
}