Cerința

Se dă o matrice cu n linii şi m coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date p numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv 0 dacă acesta nu se găseşte în matrice.

Date de intrare

Fișierul de intrare cautanrinmatrice.in conține pe prima linie numerele n şi m reprezentând dimensiunile matricei , pe următoarele n linii câte m numere aranjate conform enunţului reprezentând elementele matricei, pe următoarea linie numărul p, iar pe ultima linie cele p numere în ordine strict crescătoare ce trebuie căutate în matrice.

Date de ieșire

Fișierul de ieșire cautanrinmatrice.out va conține pe primele p linii numărul liniei şi coloanei pe care se află în matrice fiecare din cele p numere date, respectiv 0 dacă numărul nu se găseşte în matrice.

Restricții și precizări

• 1 ≤ n , m ≤ 1000
• elementele matricei sunt numere naturale mai mici decât 2.000.000.000
• 1 ≤ p ≤ 1.000.000
• cele p numere vor fi mai mici decât 2.000.000.000

Exemplu

cautanrinmatrice.in

3 4
2 5 11 14
29 27 23 19
32 38 44 59
3
11 24 38

cautanrinmatrice.out

1 3
0
3 2

Explicație

Numărul 11 se află în matrice pe linia 1 coloana 3, numărul 24 nu se află în matrice, iar numărul 38 se află în matrice pe linia 3, coloana 2.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("cautanrinmatrice.in");
ofstream cout("cautanrinmatrice.out");
int e[1000001] , n , m , p = 1 , b , x , q , a;
int cb(int val)
{
    int st = 0 , dr = p - 1 , poz = 1;
    while(st <= dr)
    {
        int m=(st+dr)/2;
        if(val <= e[m])
        {
             poz = m;
             dr = m-1;
        }
        else st = m + 1;
    }
    if(e[poz]==val) return poz;
    else return 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0 ; i < n ; ++i)
    {
        if(i%2==1)
        {
            int aux = m - 1;
            for(int j = 0 ; j < m ; ++j)
            {
                cin >> e[p+aux];
                aux--;
            }
            p+=m;
        }
        else
        {
            for(int j = 0 ; j < m ; ++j)
                cin >> e[p] , p++;
        }
    }
    cin >> q;
    for(int i = 0 ; i < q ; ++i)
    {
        cin >> x;
        if(cb(x))
        {
            int a=cb(x)/m+1;
            if(cb(x)%m==0) a--;
            int b=(cb(x))%m;
            if(b==0) b=m;
            if(a%2==0) b=m-b+1;
            cout << a << ' ' << b << '\n';
        }
       else cout << 0 << '\n';
    }
    return 0;
}