Submission #226457

#	Time	Username	Problem	Language	Result	Execution time	Memory
226457		emil_physmath	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	36 ms	504 KiB

riddicks

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using llong = long long;

int ans = 100500;
int a[5][5];
int n, m;

inline int Val_(const vector<int>& col, const vector<int>& row, bool rows)
{
    static int b[5][5];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            b[i][j] = a[i][j];
    int res = 0;
    for (int j = 0; j < m; ++j)
    {
        res += min(col[j], n - col[j]);
        vector<int> cur(n);
        for (int i = 0; i < n; ++i) cur[i] = b[i][j];
        rotate(cur.begin(), cur.begin() + col[j], cur.end());
        for (int i = 0; i < n; ++i) b[i][j] = cur[i];
    }
    for (int i = 0; i < row.size(); ++i)
    {
        res += min(row[i], m - row[i]);
        vector<int> cur(m);
        for (int j = 0; j < m; ++j) cur[j] = b[i][j];
        rotate(cur.begin(), cur.begin() + row[i], cur.end());
        for (int j = 0; j < m; ++j) b[i][j] = cur[j];
    }
    bool ans1 = true, ans2 = true;
    for (int i = 0; i < row.size(); ++i)
        for (int j = 0; j < m; ++j)
        {
            if (b[i][j] != b[i][0])
                ans1 = false;
            if (b[i][j] != b[0][j])
                ans2 = false;
        }
    bool ans = (rows ? ans1 : ans2);
    if (!ans)
        return 100500;
    return res;
}
inline int Val(const vector<int>& col, const vector<int>& row)
{
    if (col[0] == 0 && col[1] == 0 && col[2] == 0 && row[0] == 0)
        cerr << "";
    static int b[5][5];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            b[i][j] = a[i][j];
    int res = 0;
    for (int j = 0; j < m; ++j)
    {
        res += min(col[j], n - col[j]);
        vector<int> cur(n);
        for (int i = 0; i < n; ++i) cur[i] = b[i][j];
        rotate(cur.begin(), cur.begin() + col[j], cur.end());
        for (int i = 0; i < n; ++i) b[i][j] = cur[i];
    }
    for (int i = 0; i < row.size(); ++i)
    {
        res += min(row[i], m - row[i]);
        vector<int> cur(m);
        for (int j = 0; j < m; ++j) cur[j] = b[i][j];
        rotate(cur.begin(), cur.begin() + row[i], cur.end());
        for (int j = 0; j < m; ++j) b[i][j] = cur[j];
    }
    for (int i = 1; i < n; ++i)
    {
        int ires = 100500;
        for (int c = 0; c < m; ++c)
        {
            int curres = min(c, m - c);
            vector<int> cur(m);
            for (int j = 0; j < m; ++j) cur[j] = b[i][j];
            rotate(cur.begin(), cur.begin() + c, cur.end());
            bool curans = true;
            for (int j = 0; j < m; ++j)
                if (cur[j] != b[0][j])
                {
                    curans = false;
                    break;
                }
            if (curans)
                ires = min(ires, curres);
        }
        res += ires;
    }
    if (res == 0)
        cerr << "";
    return res;
}
void Solve(vector<int>& col, vector<int>& row)
{
    if (col.size() == m && row.size() == 0)
    {
        row.resize(n);
        ans = min(ans, Val_(col, row, true));
        row.clear();
    }
    if (col.size() == m && row.size() == /*n*/1)
    {
        ans = min(ans, Val(col, row));
        return;
    }
    if (col.size() == m)
    {
        row.push_back(0);
        for (row.back() = 0; row.back() < m; ++row.back())
            Solve(col, row);
        row.pop_back();
    }
    else
    {
        col.push_back(0);
        for (col.back() = 0; col.back() < n; ++col.back())
            Solve(col, row);
        col.pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    vector<int> col, row;
    Solve(col, row);
    cout << ans;
}

Compilation message (stderr)

riddicks.cpp: In function 'int Val_(const std::vector<int>&, const std::vector<int>&, bool)':
riddicks.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < row.size(); ++i)
                     ~~^~~~~~~~~~~~
riddicks.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < row.size(); ++i)
                     ~~^~~~~~~~~~~~
riddicks.cpp: In function 'int Val(const std::vector<int>&, const std::vector<int>&)':
riddicks.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < row.size(); ++i)
                     ~~^~~~~~~~~~~~
riddicks.cpp: In function 'void Solve(std::vector<int>&, std::vector<int>&)':
riddicks.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (col.size() == m && row.size() == 0)
         ~~~~~~~~~~~^~~~
riddicks.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (col.size() == m && row.size() == /*n*/1)
         ~~~~~~~~~~~^~~~
riddicks.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (col.size() == m)
         ~~~~~~~~~~~^~~~

• Subtask 1: 100 / 100