Cod sursa(job #2786513)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 21 octombrie 2021 09:18:43
Problema Cautare binara Scor 60
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>

#define MAX_N 100000

int v[MAX_N];

int main() {
    FILE *fin, *fout;
    int n, q, tip, x, p2, p, pas, i;

    fin = fopen( "cautbin.in", "r" );

    fscanf( fin, "%d", &n );
    for ( i = 0; i < n; i++ )
        fscanf( fin, "%u", &v[i] );

    p2 = 1;
    while ( (p2 << 1) < n )
        p2 <<= 1;

    fout = fopen( "cautbin.out", "w" );

    fscanf( fin, "%d", &q );
    for ( i = 0; i < q; i++ ) {
        fscanf( fin, "%d%d", &tip, &x );

        if ( tip == 0 ) {
            pas = p2;
            p = 0;
            while ( pas > 0 ) {
                if ( p + pas < n && v[p + pas] <= x )
                    p += pas;
                pas >>= 1;
            }

            fprintf( fout, "%d\n", v[p] == x ? p + 1 : -1 );
        }
        else if ( tip == 1 ) {
            pas = p2;
            p = 0;
            while ( pas > 0 ) {
                if ( p + pas < n && v[p + pas] <= x )
                    p += pas;
                pas >>= 1;
            }

            fprintf( fout, "%d\n", p + 1 );
        }
        else {
            pas = p2;
            p = 0;
            while ( pas > 0 ) {
                if ( p + pas < n && v[p + pas] < x )
                    p += pas;
                pas >>= 1;
            }

            fprintf( fout, "%d\n", p + 2 <= n ? p + 2 : n );
        }
    }

    fclose( fin );
    fclose( fout );

    return 0;
}