Submission #894530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894530	2023-12-28T11:40:18 Z	heeheeheehaaw	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	61 ms	440 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	21 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	3 ms	348 KB	Output is correct
9	Correct	44 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Correct	45 ms	348 KB	Output is correct
12	Correct	5 ms	436 KB	Output is correct
13	Correct	57 ms	348 KB	Output is correct
14	Correct	57 ms	348 KB	Output is correct
15	Correct	57 ms	348 KB	Output is correct
16	Correct	61 ms	344 KB	Output is correct
17	Correct	56 ms	344 KB	Output is correct
18	Correct	55 ms	344 KB	Output is correct
19	Correct	56 ms	412 KB	Output is correct
20	Correct	55 ms	348 KB	Output is correct