oj.uz

Submission #26760

# Submission time Handle Problem Language Result Execution time Memory
26760 2017-07-05T12:08:50 Z RayaBurong25_1 medians (balkan11_medians) C++14
10 / 100
 39 ms 3068 KB 
#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 <= N; 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

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
10.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3068 KB Output is correct
2 Incorrect 0 ms 3068 KB Output isn't correct
3 Incorrect 0 ms 3068 KB Output isn't correct
4 Incorrect 0 ms 3068 KB Output isn't correct
5 Incorrect 0 ms 3068 KB Output isn't correct
6 Correct 0 ms 3068 KB Output is correct
7 Incorrect 0 ms 3068 KB Output isn't correct
8 Incorrect 0 ms 3068 KB Output isn't correct
9 Incorrect 0 ms 3068 KB Output isn't correct
10 Incorrect 0 ms 3068 KB Output isn't correct
11 Incorrect 0 ms 3068 KB Output isn't correct
12 Incorrect 0 ms 3068 KB Output isn't correct
13 Incorrect 0 ms 3068 KB Output isn't correct

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3068 KB Output isn't correct
2 Incorrect 0 ms 3068 KB Output isn't correct
3 Incorrect 3 ms 3068 KB Output isn't correct
4 Incorrect 6 ms 3068 KB Output isn't correct
5 Incorrect 16 ms 3068 KB Output isn't correct
6 Incorrect 19 ms 3068 KB Output isn't correct
7 Incorrect 39 ms 3068 KB Output isn't correct