Submission #26764

#	Time	Username	Problem	Language	Result	Execution time	Memory
26764		RayaBurong25_1	medians (balkan11_medians)	C++14	100 / 100	49 ms	3068 KiB

medians

#include <stdio.h>
int B[100005];
int Used[200005];
int Fen[200005];
int min, max;
int N;
int Query(int pos)
{
    int sum = 0;
    for (; pos > 0; pos -= pos&-pos)
        sum += Fen[pos];
    return sum;
}
void Update(int pos)
{
    Used[pos] = 1;
    for (; pos <= 2*N - 1; pos += pos&-pos)
        Fen[pos]++;
}
int main()
{
    scanf("%d", &N);
    min = 1;
    max = 2*N - 1;
    int i, r, cnt;
    for (i = 0; i < N; i++)
        scanf("%d", &B[i]);
    for (i = 0; i < N; i++)
    {
        // printf("i%d ", i);
        cnt = 0;
        if (!Used[B[i]])
        {
            Used[B[i]] = 1;
            Update(B[i]);
            printf("%d ", B[i]);
            cnt++;
        }
        r = Query(B[i]);
        // printf("//%d//", r);
        if (i == 0)
            continue;
        if (cnt == 1)
        {
            if (r < i + 1)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
            }
            else
            {
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
        }
        else
        {
            if (r == i - 1)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
            }
            else if (r == i)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
            else
            {
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
        }
    }
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:22:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
medians.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &B[i]);
                           ^

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35