oj.uz

Submission #803712

# Submission time Handle Problem Language Result Execution time Memory
803712 2023-08-03T05:36:01 Z moel_solution(#10136) Shifty Grid (CCO17_shifty) C++17
5 / 25
 87 ms 2020 KB 
#include<bits/stdc++.h>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int mp[105][105];
int tmp[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>mp[i][j];
    vector<pair<int,pi> >rans;
    auto roth=[&](int r,int p)->void
    {
        p=(p%m+m)%m;
        if(p==0)
            return;
        rans.eb(1,pi(r+1,p));
        for(int i=0;i<m;i++)
            tmp[(i+p)%m]=mp[r][i];
        for(int i=0;i<m;i++)
            mp[r][i]=tmp[i];
        return;
    };
    auto rotv=[&](int c,int p)->void
    {
        p=(p%n+n)%n;
        if(p==0)
            return;
        rans.eb(2,pi(c+1,p));
        for(int i=0;i<n;i++)
            tmp[(i+p)%n]=mp[i][c];
        for(int i=0;i<n;i++)
            mp[i][c]=tmp[i];
        return;
    };
    auto find=[&](int x)->pi
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(mp[i][j]==x)
                    return pi(i,j);
        return pi(-1,-1);
    };
    auto find2=[&](int x)->int
    {
        for(int j=0;j<m;j++)
            if(mp[n-1][j]==x)
                return j;
        return -1;
    };
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<m;j++)
        {
            int x=i*m+j;
            pi ps=find(x);
            if(ps.fi==i)
            {
                rotv(ps.se,1);
                roth(i+1,1);
                rotv(ps.se,-1);
                ps.fi++,ps.se++;
            }
            roth(ps.fi,j-ps.se);
            roth(ps.fi,1);
            rotv(j,ps.fi-i);
            roth(ps.fi,-1);
            rotv(j,i-ps.fi);
#ifdef LOCAL
            cout<<"RESULT AFTER "<<x<<": "<<endl;
            for(int i=0;i<n;i++,cout<<endl)
                for(int j=0;j<m;j++)
                    cout<<mp[i][j]<<' ';
#endif
        }
    }
    int z=n*m-m;
    auto swp=[&](int i,int j)->void
    {
        if(i==j)
            return;
        rotv(i,n/2);
        roth(n-1,i-j);
        rotv(i,n/2);
        roth(n-1,j-i);
        rotv(i,n/2);
        return;
    };
    for(int i=0;i<m;i++)
        swp(i,find2(z+i));
    if(mp[0][0]!=0)
    {
        roth(n-1,1);
        for(int i=0;i<m;i++)
            swp(i,find2(z+i));
    }
#ifdef LOCAL
    cout<<"RESULT: "<<endl;
    for(int i=0;i<n;i++,cout<<endl)
        for(int j=0;j<m;j++)
            cout<<mp[i][j]<<' ';
#endif
    assert(rans.size()<=100'000);
    cout<<rans.size()<<'\n';
    for(auto&t:rans)
        cout<<t.fi<<' '<<t.se.fi<<' '<<t.se.se<<'\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 84 ms 1956 KB Output is correct
6 Incorrect 87 ms 2020 KB Contestant's solution is invalid
7 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 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 84 ms 1956 KB Output is correct
18 Incorrect 87 ms 2020 KB Contestant's solution is invalid
19 Halted 0 ms 0 KB -