Submission #894530

#	Time	Username	Problem	Language	Result	Execution time	Memory
894530		heeheeheehaaw	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	61 ms	440 KiB

riddicks

#include <bits/stdc++.h>

using namespace std;

int a[8][8];
int v[8][8];
int init[8][8];
int curr[8][8];
int aux[8][8];
int rez = 100500;
vector<int> moves;
int n, m;

void colsus(int j)
{
    for(int i = 2; i <= n; i++)
        swap(v[i - 1][j], v[i][j]);
}

void coljos(int j)
{
    for(int i = n - 1; i >= 1; i--)
        swap(v[i][j], v[i + 1][j]);
}

void linst(int i)
{
    for(int j = 2; j <= m; j++)
        swap(v[i][j], v[i][j - 1]);
}

void lindr(int i)
{
    for(int j = m - 1; j >= 1; j--)
        swap(v[i][j], v[i][j + 1]);
}

void linauxdr(int i)
{
    for(int j = m - 1; j >= 1; j--)
        swap(aux[i][j], aux[i][j + 1]);
}

void linauxst(int i)
{
    for(int j = 2; j <= m; j++)
        swap(aux[i][j], aux[i][j - 1]);
}

void solve()
{
    bool ok = false;
    int ans = 0, fin = 1e9;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            v[i][j] = a[i][j];

    for(int i = 1; i <= m; i++)
    {
        int nr = moves[i - 1];
        ans += abs(nr);
        while(nr < 0) colsus(i), nr++;
        while(nr > 0) coljos(i), nr--;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            init[i][j] = v[i][j];

    for(int nr = 0; nr < m; nr++)
    {
        bool ver = true;
        for(int i = 2; i <= n; i++)
        {
            bool altcv = false;
            for(int j = 0; j < m; j++)
            {
                bool sper = true;
                for(int k = 1; k <= m; k++)
                    if(v[i][k] != v[1][k])
                        sper = false;
                if(sper == true)
                    altcv = true;
                lindr(i);
            }

            if(altcv == false)
                ver = false;
        }

        if(ver == true)
        {
            int sper = ans;
            ok = true;
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    aux[i][j] = init[i][j];

            for(int i = 1; i <= n; i++)
            {
                int minn = 5;
                for(int cnt = 0; cnt < m; cnt++)
                {
                    bool ver = true;
                    for(int j = 1; j <= m; j++)
                        if(aux[i][j] != v[1][j])
                            ver = false;
                    if(ver) minn = min(minn, cnt);
                    linauxdr(i);
                }

                for(int cnt = 0; cnt < m; cnt++)
                {
                    bool ver = true;
                    for(int j = 1; j <= m; j++)
                        if(aux[i][j] != v[1][j])
                            ver = false;
                    if(ver) minn = min(minn, cnt);
                    linauxst(i);
                }

                sper += minn;
            }

            rez = min(rez, sper);
        }

        lindr(1);
    }

    return;
}

void backt(int poz)
{
    if(poz > m)
    {
        solve();
        return;
    }

    for(int i = -4; i <= 4; i++)
    {
        moves.push_back(i);
        backt(poz + 1);
        moves.pop_back();
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    backt(1);
    cout<<rez;
    return 0;
}

Compilation message (stderr)

riddicks.cpp: In function 'void solve()':
riddicks.cpp:52:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   52 |     bool ok = false;
      |          ^~
riddicks.cpp:53:18: warning: unused variable 'fin' [-Wunused-variable]
   53 |     int ans = 0, fin = 1e9;
      |                  ^~~

• Subtask 1: 100 / 100