QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#617760#5113. Bridgemhw#WA 422ms28604kbC++201.8kb2024-10-06 16:58:172024-10-06 16:58:18

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 16:58:18]
  • 评测
  • 测评结果:WA
  • 用时:422ms
  • 内存:28604kb
  • [2024-10-06 16:58:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

int n, m, b, q;
void slv(){
    cin >> n >> m >> q;
    int b = sqrt(m) + 2;
    vector<int> l(m + 1), r(m + 1);

    int cnt = 0;
    for(int i = 1; i <= m; ++i) {
        l[i] = (i - 1) * b + 1, r[i] = i * b;
        if(r[i] >= m) {
            r[i] = m;
            cnt = i;
            break;
        } 
    }

    vector<vector<int> >g(n + 1, vector<int>(cnt + 1));
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= cnt; ++j){
            g[i][j] = i;
        }
    }

    int op, x, y;
    unordered_map<int, int> v1, v2;
    //v1代表有↓,v2代表有↑
    while(q--){
        cin >> op;
        if(op == 2){
            cin >> x;
            for(int j = 1; j <= cnt; ++j){
                x = g[x][j];
            }
            cout << x << '\n';
        } else {
            cin >> x >> y;
            v1[x * m + y] = 1;
            v2[(x + 1) * m + y] = 1;
            int now_b = (y - 1) / b + 1, x1, x2;//影响哪个块
            //x, y

            x1 = x;
            for(int j = y - 1; j >= l[now_b]; --j){
                if(v2[x1 * m + j]) x1--;
                else if(v1[x1 * m + j]) x1++;
            }
            
            //x + 1, y
            x2 = x + 1;
            for(int j = y - 1; j >= l[now_b]; --j){
                if(v2[x2 * m + j]) x2--;
                if(v1[x2 * m + j]) x2++;
            }
            swap(g[x1][now_b], g[x2][now_b]);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1; // cin >> T;
    while (_--) slv();
    return 0;
}
/*
3 4 13
2 2
1 1 3
2 1
2 2
2 3
1 2 4
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

input:

3 4 13
2 2
1 1 3
2 1
2 2
2 3
1 2 4
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

output:

2
2
1
3
3
1
2
3
2
1

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 422ms
memory: 28604kb

input:

3 100000 99997
2 2
2 2
2 3
2 3
2 3
2 3
2 3
1 2 11047
1 1 98732
1 2 90045
1 1 43556
2 1
2 3
1 2 17242
1 1 17027
2 1
1 1 94195
2 1
2 2
2 1
2 3
1 1 34124
1 2 14354
1 2 673
1 2 39812
1 2 35520
1 2 16046
2 3
2 2
1 1 25410
2 3
2 1
2 3
2 2
1 2 55684
2 1
1 2 24811
1 2 92268
1 2 60268
2 2
1 1 89272
1 2 19232...

output:

2
2
3
3
3
3
3
3
2
1
2
1
2
3
3
1
1
2
1
3
3
2
1
3
2
1
2
1
2
2
2
2
1
1
2
1
3
2
1
3
2
1
2
2
2
3
1
1
2
1
3
2
1
2
3
3
2
1
2
3
3
1
3
1
3
2
2
1
2
1
2
3
2
1
2
1
1
2
3
3
2
2
3
2
2
1
1
1
2
3
3
1
1
2
1
1
3
3
1
2
1
2
1
1
1
3
2
1
1
1
3
1
1
3
3
1
2
3
1
3
3
2
2
1
2
2
3
2
2
3
3
3
3
2
1
1
3
3
2
1
1
3
2
1
1
2
2
2
3
2
...

result:

wrong answer 43rd numbers differ - expected: '3', found: '2'