Cod sursa(job #2918094)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 9 august 2022 19:55:31
Problema Cautare binara Scor 60
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <math.h>
#include <stdio.h>
#define NMAX 100000 + 1

FILE *fin, *fout;

int n, v[NMAX];

int max_2power_less_than(int x) {
    int power = 1;
    while (power < x) power <<= 1;
    return power;
}

// max i such that v[i] <= x
int rightmost_smaller_or_eq_than_element(int x) {
    int i = 0, step = max_2power_less_than(n);
    while (step) {
        if (i + step < n && v[i + step] <= x) {
            i += step;
        }
        step >>= 1;
    }
    return i;
}

// max i such that v[i] < x
int rightmost_smaller_than_element(int x) {
    int i = 0, step = max_2power_less_than(n);
    while (step) {
        if (i + step < n && v[i + step] < x) {
            i += step;
        }
        step >>= 1;
    }
    return i;
}

// max i such that v[i] == x or -1 if no such x
int bin0(int x) {
    int index = rightmost_smaller_or_eq_than_element(x);
    return (v[index] == x ? index : -1);
}

// max i such that v[i] <= x
int bin1(int x) {
    return rightmost_smaller_or_eq_than_element(x);
}

// min i such that v[i] >= x
// == 1 + (max i such that v[i] < x)
int bin2(int x) {
    return 1 + rightmost_smaller_than_element(x);
}

int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");

    fscanf(fin, "%d", &n);
    for (int i = 1; i <= n; ++i) {
        fscanf(fin, "%d", &v[i]);
    }

    int opt, arg, queries;
    fscanf(fin, "%d", &queries);

    for (int i = 0; i < queries; ++i) {
        fscanf(fin, "%d", &opt);
        fscanf(fin, "%d", &arg);

        switch (opt) {
            case 0: {
                fprintf(fout, "%d\n", bin0(arg));
                break;
            }
            case 1: {
                fprintf(fout, "%d\n", bin1(arg));
                break;
            }
            case 2: {
                fprintf(fout, "%d\n", bin2(arg));
            }
        }
    }

    return 0;
}