Koordinate

Data je matrica \(\mathbf{A}\) dimenzija \(n \times m\) u kojoj su sve vrste i sve kolone sortirane neopadajuće (mogući su duplikati). Za zadatu vrednost \(x\) proveriti da li se \(x\) pojavljuje u matrici, i ispisati koordinate (red, kolona) njene leksikografski prve pojave (sa najmanjim indeksom reda, a u tom redu sa najmanjim indeksom kolone).

Opis ulaza

Sa standardnog ulaza se unose dimenzije matrice \(n\) i \(m\) (\(1 \leq n, m \leq 1000\)) i broj upita \(q\) (\(1 \leq q \leq 10^6\)). Zatim, u narednih \(n\) redova unosi se po \(m\) celih brojeva \(\mathbf{A}_{i, j}\) (\(10^5 < \mathbf{A}_{i, j} < 10^5, 1 \leq i \leq n, 1 \leq j \leq n\)). Nakon toga, unosi se \(q\) traženih celih brojeva \(x_k\) (\(-10^5 < x_k < 10^5, 1 \leq k \leq q\)).

Opis izlaza

Na standardni izlaz, za svaki upit \(x_k\), ispisati koordinate leksikografski prvog pojavljivanja broja \(x_k\), ukoliko se broj \(x_k\) ne pojavljuje u matrici \(\mathbf{A}\) ispisati -1.

Primer 1

Ulaz

3 4 3
1 2 4 7
2 4 4 8
3 5 9 10
4
5
2

Izlaz

1 3
3 2
1 2

Objašnjenje

Vrednost 4 se prvi put javlja u redu 1 i koloni 3. Vrednost 5 se jedino javlja u redu 3 i koloni 2. Vrednost 2 se prvi put javlja u redu 1 i koloni 2.

Primer 2

Ulaz

2 3 2
-1 0 1
2 3 5
6
0

Izlaz

-1
1 2

Objašnjenje

Vrednost 6 se ne nalazi u matrici. Vrednost 0 se jedino javlja u redu 1 i koloni 2.

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>

using namespace std;

void max_coord(const vector<vector<int>> &A, const int x)
{
    int n = A.size(), m = A[0].size();
    int i = 0, j = m - 1;
    int row = -1, col = -1;

    bool found = false;

    while (i < n && j >= 0) {
        if (A[i][j] < x) {
            i++;
            if (found) break;
        } else if (A[i][j] > x) {
            j--;
        } else { // A[i][j] = x
            found = true;
            row = i; 
            col = j--;
        }
    }
    if (found) {
        cout << row + 1 << " " << col + 1 << endl;
    } else {
        cout << -1 << endl;
    }
}

int main() 
{
    int n, m, q; cin >> n >> m >> q;

    vector<vector<int>> A(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }

    while (q--) {
        int x; cin >> x;
        max_coord(A, x);
    }

    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

void max_coord(const vector<vector<int>> &A, const int x)
{
    int n = A.size(), m = A[0].size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (A[i][j] == x) { 
                cout << i + 1 << " " << j + 1 << endl;
                return;
            }
        }
    }

    cout << -1 << endl;
}

int main() 
{
    int n, m, q; cin >> n >> m >> q;

    vector<vector<int>> A(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }

    while (q--) {
        int x; cin >> x;
        max_coord(A, x);
    }

    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

void max_coord(const vector<vector<int>> &A, const int x)
{
    int n = A.size();

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(A[i].begin(), A[i].end(), x);
        if (it != A[i].end() && *it == x) {
            int j = it - A[i].begin();
            cout << i + 1 << " " << j + 1 << endl;
            return;
        }
    }

    cout << -1 << endl;
}

int main() 
{
    int n, m, q; cin >> n >> m >> q;

    vector<vector<int>> A(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }

    while (q--) {
        int x; cin >> x;
        max_coord(A, x);
    }

    return 0;
}