oj.uz

Submission #804088

# Submission time Handle Problem Language Result Execution time Memory
804088 2023-08-03T07:07:25 Z 이동현(#10103) Shifty Grid (CCO17_shifty) C++17
0 / 25
 941 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector<array<int, 2>> pos(n * m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> a[i][j];
            pos[a[i][j]] = {i, j};
        }
    }

    vector<vector<int>> ans;

    auto rotr = [&](int row)->void{
        int imsi = a[row][m - 1];
        for(int i = m - 1; i > 0; --i){
            a[row][i] = a[row][i - 1];
        }
        a[row][0] = imsi;
        for(int i = 0; i < m; ++i){
            pos[a[row][i]] = {row, i};
        }
    };

    auto rotrt = [&](int now, int t)->void{
        if(t) ans.push_back({0, now, t});
        while(t--) rotr(now);
    };

    auto rotc = [&](int col)->void{
        int imsi = a[n - 1][col];
        for(int i = n - 1; i > 0; --i){
            a[i][col] = a[i - 1][col];
        }
        a[0][col] = imsi;
        for(int i = 0; i < n; ++i){
            pos[a[i][col]] = {i, col};
        }
    };

    auto rotct = [&](int now, int t)->void{
        if(t) ans.push_back({1, now, t});
        while(t--) rotc(now);
    };

    auto toleft = [&](array<int, 2> pos, int torow){
        rotrt(pos[0], m - pos[1]);
        rotct(0, 1);
        rotrt(pos[0], pos[1]);
        rotct(0, (torow - pos[0] - 1 + n * 2) % n);
    };

    auto output = [&](){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        cout << endl;
    };

    for(int i = n - 1; i >= 0; --i){
        for(int j = 1; j < m; ++j){
            toleft(pos[i * m + m - j], i);
            rotrt(i, 1);
        
            // output();
        }
    }

    for(int i = n - 1; i > 0; --i){
        int id = i * m;

        if(pos[id][1] == 0){
            int sv = pos[id][0];
            rotct(0, n - sv);
            rotrt(0, m - 1);
            rotct(0, (sv - i + n) % n);
            rotrt(0, 1);
            rotct(0, i);
        }
        else{
            rotct(0, n - i);
            rotrt(0, m - 1);
            rotct(0, i);
            rotrt(0, 1);
        }

        // output();

        // cout << "HI" << endl;
    }

    auto ok = [&](){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(a[i][j] != i * m + j){
                    return 0;
                }
            }
        }
        return 1;
    };

    while(!ok()){
        rotct(0, 1);
        rotrt(0, m - 1);
        rotct(0, 1);
        rotrt(0, 1);
    }

    cout << (int)ans.size() << '\n';
    for(auto&i:ans){
        cout << i[0] + 1 << ' ' << i[1] + 1 << ' ' << i[2] << '\n';
    }
    
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:64:10: warning: variable 'output' set but not used [-Wunused-but-set-variable]
   64 |     auto output = [&](){
      |          ^~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 941 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 852 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 941 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -