11053: 【原1053】二哥的内存

题目

题目描述

author: zyz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1053

Description

二哥买了一台内存非常非常大的电脑，以至于二哥写程序直接开了一个 100,000 * 100,000 的数组都跑得很顺畅。这个数组初始被清零，二哥在其中的 n 个位置赋了值，然后他做了 m 次操作，每次操作为以下三个指令之一：

0 x y ：交换数组的 x 行与 y 行

1 x y ：交换数组的 x 列与 y 列

2 x y ：读取数组当期 x 行 y 列的数

现在请你写一个程序，对于每次读取，输出内存中对应位置的数。

Input Format

第 1 行：一个整数 n 表示初始化了 n 个位置。

第 2..n+1 行：每行三个整数： x y z 表示数组中 x 行 y 列的值被赋值为 z。

第 n+2 行：一个整数 m 表示操作的数量

第 n+3..n+m+2 行：每行一条指令 op x y，其中 op 为 0 表示交换行，op 为 1 表示交换列，op 为 2 表示读取操作。

数组中一个位置不会被赋值两次。

Output Format

对于每个读取指令，输出一行一个整数，为内存中对应位置的数。

Hint

对 70% 的数据，数组行列的下标范围为 0..199,\(0 \leq n \leq 1000\), \(0 \leq m \leq 2000\).

对 100% 的数据，数组行列的下标范围为 0..99999, \(0 \leq n \leq 10000\), \(0 \leq m \leq 20000\).

Sample Input

3
0 1 1
1 0 2
2 2 3
9
0 0 1
2 0 0
2 1 1
2 2 2
1 0 1
0 0 1
2 0 0
2 1 1
2 2 2

Sample Output

2
1
3
1
2
3

FineArtz's solution

/* 二哥的内存 */
#include <iostream>
#include <algorithm>
using namespace std;

class Point{
public:
    Point(int xx = -1, int yy = -1, int d = 0) : x(xx), y(yy), data(d) {}
    bool operator <(const Point &p){
        return (x < p.x || (x == p.x && y < p.y));
    }

    int x = -1, y = -1, data = 0;
};

Point a[10005];
int mapx[100005], mapy[100005];
int n, m;

void qsort(int low, int high){
    int l = low, h = high;
    Point key = a[low];
    while (l < h){
        while (l < h && key < a[h]) --h;
        a[l] = a[h];
        while (l < h && a[l] < key) ++l;
        a[h] = a[l];
    }
    a[l] = key;
    if (low < l)
        qsort(low, l - 1);
    if (high > h)
        qsort(h + 1, high);
}

int find(int x, int y){
    Point t(x, y);
    auto it = lower_bound(a + 1, a + n + 1, t);
    if (it != a + n + 1 && it->x == x && it->y == y)
        return it->data;
    else
        return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < 100005; ++i){
        mapx[i] = i;
        mapy[i] = i;
    }
    for (int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].y >> a[i].data;
    qsort(1, n);
    cin >> m;
    while (m--){
        int op, x, y, t;
        cin >> op >> x >> y;
        switch(op){
        case 0:
            t = mapx[x];
            mapx[x] = mapx[y];
            mapx[y] = t;
            break;
        case 1:
            t = mapy[x];
            mapy[x] = mapy[y];
            mapy[y] = t;
            break;
        case 2:
            cout << find(mapx[x], mapy[y]) << '\n';
            break;
        }
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cmath"
#include "cstdio"
using namespace std;

constexpr int NUM_SIZE = 100009;
constexpr int HASH_MAX = 500000;

//数据存放类
class data_type {
public:
    int x = -1, y = -1, val = 0;
};

//简易哈希表
class hash_map {
public:
    data_type hash_data[HASH_MAX]{};

    //哈希函数
    int hash_func(int key1, int key2) {
        return ((unsigned int)(key1 * key2)) % (unsigned int)HASH_MAX;
    }

    //寻找
    int find(int key1, int key2) {
        for (auto p = hash_func(key1, key2);; p = (p + 1) % HASH_MAX) {
            if (hash_data[p].x == key1 && hash_data[p].y == key2) {
                return hash_data[p].val;
            }
            else if (hash_data[p].x < 0) {
                return 0;
            }
        }
    }

    //插入
    void insert(int key1, int key2, int val) {
        for (auto p = hash_func(key1, key2);; p = (p + 1) % HASH_MAX) {
            if (hash_data[p].x < 0) {
                hash_data[p].x = key1;
                hash_data[p].y = key2;
                hash_data[p].val = val;
                break;
            }
        }
    }
};

//映射关系
int row[NUM_SIZE], col[NUM_SIZE];
hash_map map_data;

int main() {
    //初始化映射关系
    for (int i = 0; i < NUM_SIZE; ++i) {
        row[i] = i;
        col[i] = i;
    }

    int n, m;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        map_data.insert(x, y, z);
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op == 0) {
            auto temp = row[x];
            row[x] = row[y];
            row[y] = temp;
        }
        else if (op == 1) {
            auto temp = col[x];
            col[x] = col[y];
            col[y] = temp;
        }
        else {
            printf("%d\n", map_data.find(row[x], col[y]));
        }
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

struct Node {
    int row;
    int colume;
    int data;

    bool operator<(Node &right) {
        if (row != right.row) {
            return row < right.row;
        } else {
            return colume < right.colume;
        }
    }

    bool operator>(Node &right) {
        if (row != right.row) {
            return row > right.row;
        } else {
            return colume > right.colume;
        }
    }
};

Node arr[maxN];
int row[maxN] = {0}, col[maxN] = {0};

void qSort(Node *, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int r, c, d;
        cin >> r >> c >> d;

        arr[i].row = r;
        arr[i].colume = c;
        arr[i].data = d;
    }

    qSort(arr, 0, n - 1);

    for (int i = 0; i < maxN; i++) {
        row[i] = i;
        col[i] = i;
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        int order, x, y, temp;
        cin >> order >> x >> y;
        switch (order) {
            case 0:
                temp = row[x];
                row[x] = row[y];
                row[y] = temp;
                break;
            case 1:
                temp = col[x];
                col[x] = col[y];
                col[y] = temp;
                break;
            case 2:
                int r = row[x], c = col[y];
                bool flag = 0;
                for (int i = 0; i < n; i++) {
                    if (arr[i].row == r && arr[i].colume == c) {
                        cout << arr[i].data << '\n';
                        flag = 1;
                    }
                }
                if (!flag) {
                    cout << 0 << '\n';
                }
        }
    }

    return 0;
}

void qSort(Node *nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    Node key = nums[first];

    while (first < last) {
        while (first < last && nums[last] > key) {
            --last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] < key) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    qSort(nums, l, first - 1);
    qSort(nums, first + 1, h);
}

yyong119's solution

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100001;
struct Point {
    int x, y, z;
}points[MAXN];
int n;
int curx[MAXN], cury[MAXN];

bool comp(const Point& a, const Point& b){

    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

int find(int x,int y){

    Point tofind;
    tofind.x = x; tofind.y = y;
    Point* f = lower_bound(points, points+n, tofind, comp);
    if((f != points+n) && (f->x == x) && (f->y == y)) return f->z;
    return 0;
}

int main() {
    int m, op, x, y;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d %d", &points[i].x, &points[i].y, &points[i].z);
    for (int i = 0; i < MAXN; ++i) curx[i] = i;
    for (int i = 0; i < MAXN; ++i) cury[i] = i;
    scanf("%d", &m);
    sort(points, points + n, comp);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &op, &x, &y);
        if(op == 0) {
            swap(curx[x], curx[y]);
        } else if(op == 1)
            swap(cury[x], cury[y]);
        else{
            printf("%d\n", find(curx[x], cury[y]));
        }
    }
    return 0;
}