Submission #47629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47629	2018-05-06T04:43:15 Z	fallingstar	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	7 ms	620 KB

riddicks

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int NO_SOLUTION = 100500;

int n, m, a[5][5], b[5][5];
int complexity = NO_SOLUTION;

void ShiftCols(int);

void ShiftRows(int row, int steps)
{
    if (row == m)
    {
        auto check = [&] {
            for (int i = 0; i < n; ++i)
                for (int j = 1; j < m; ++j)
                    if (b[j][i] != b[0][i]) return false;
            return true;
        };
        if (check())
            complexity = min(complexity, steps);
        ShiftCols(steps);
    }
    else
        for (int i = 0; i < n; ++i)                     // position of row "row"
        {
            copy(a[row], a[row] + n, b[row]);
            rotate(b[row], b[row] + i, b[row] + n);
            ShiftRows(row + 1, steps + min(i, n - i));
        }
}

int c[5][5];

void ShiftCols(int steps)       // swap x and y again -> actually shifting rows
{
    for (int i = 0; i < m; ++i)                   // position of first row
    {
        // row 0 of c is col 0 of b
        for (int j = 0; j < m; ++j)
            c[0][j] = b[j][0];
        rotate(c[0], c[0] + i, c[0] + m);

        auto calc = [&] {
            int tot_cost = 0;                     // cost for this fixed first row
            for (int i = 1; i < n; ++i)           // for each row 1 -> n - 1
            {
                int row_cost = NO_SOLUTION;       // cost for i-th row
                for (int j = 0; j < m; ++j)       // position of i-th row
                {
                    // row i of c is col i of b
                    for (int k = 0; k < m; ++k)
                        c[i][k] = b[k][i];
                    rotate(c[i], c[i] + j, c[i] + m);
                    if (equal(c[0], c[0] + m, c[i]))
                        row_cost = min(row_cost, min(j, m - j));
                }
                if (row_cost == NO_SOLUTION)
                    return NO_SOLUTION;
                tot_cost += row_cost;
            }
            return tot_cost;
        };
        complexity = min(complexity, steps + min(i, m - i) + calc());
    }
}

int main()
{
    cin >> n >> m;
    vector<int> values;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            cin >> a[j][i];                 // swap x and y -> shift rows then columns
            values.push_back(a[j][i]);
        }
    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());
    if (values.size() > max(n, m))
    {
        cout << NO_SOLUTION;
        return 0;
    }

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
        {
            a[i][j] = lower_bound(values.begin(), values.end(), a[i][j]) - values.begin();
            b[i][j] = a[i][j];              // copy of a
        }
    ShiftRows(0, 0);
    cout << complexity;
    return 0;
}

Compilation message

riddicks.cpp: In function 'int main()':
riddicks.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (values.size() > max(n, m))
         ~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	556 KB	Output is correct
7	Correct	2 ms	556 KB	Output is correct
8	Correct	2 ms	556 KB	Output is correct
9	Correct	3 ms	556 KB	Output is correct
10	Correct	2 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	2 ms	556 KB	Output is correct
13	Correct	5 ms	556 KB	Output is correct
14	Correct	5 ms	556 KB	Output is correct
15	Correct	5 ms	556 KB	Output is correct
16	Correct	5 ms	556 KB	Output is correct
17	Correct	5 ms	596 KB	Output is correct
18	Correct	5 ms	596 KB	Output is correct
19	Correct	7 ms	596 KB	Output is correct
20	Correct	5 ms	620 KB	Output is correct