Submission #73388411

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <climits>
#include <limits.h>
#include <assert.h>
#include <numeric>
using namespace std;

using ll = long long;
const ll mod = 1e9 + 7;
ll gridN = 0;

#define cy cout << "Yes\n"
#define cn cout << "No\n"
#define na cout << "-1\n"

pair<ll, ll> getCoords(ll num)
{
    ll r = (num - 1) / gridN + 1;
    ll c = (num - 1) % gridN + 1;
    return {r, c};
}

ll getNumber(ll r, ll c)
{
    return (r - 1) * gridN + c;
}

void permutations(vector<vector<ll>> &res, vector<ll> arr, ll idx)
{
    if (idx == arr.size())
    {
        res.push_back(arr);
        return;
    }
    for (ll i = idx; i < arr.size(); i++)
    {
        swap(arr[idx], arr[i]);
        permutations(res, arr, idx + 1);
        swap(arr[idx], arr[i]);
    }
}

// Function to get the permutations
vector<vector<ll>> permuteDist(vector<ll> &arr)
{
    vector<vector<ll>> res;
    permutations(res, arr, 0);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, m;
    cin >> n >> m;
    gridN = n;
    ll start, end;
    cin >> start >> end;
    vector<ll> P(m);
    for (ll i = 0; i < m; i++)
        cin >> P[i];

    vector<vector<ll>> allperms = permuteDist(P);

    ll mini = LLONG_MAX;
    for (auto &p : allperms)
    {
        ll s = start, t = end;
        ll total = 0;

        for (ll i = 0; i < m; i++)
        {
            pair<ll, ll> p1 = getCoords(s), p2 = getCoords(p[i]);
            ll r1 = p1.first, c1 = p1.second;
            ll r2 = p2.first, c2 = p2.second;

            ll dist = abs(r2 - r1) + abs(c2 - c1);
            // cout << r1 << " " << c1 << " " << r2 << " " << c2 << " " << dist << '\n';
            s = p[i];
            total += dist;
        }
        pair<ll, ll> p1 = getCoords(s), p2 = getCoords(t);
        ll r1 = p1.first, c1 = p1.second;
        ll r2 = p2.first, c2 = p2.second;
        
        ll dist = abs(r2 - r1) + abs(c2 - c1);
        // cout << r1 << " " << c1 << " " << r2 << " " << c2 << dist << '\n';
        s = t;
        total += dist;
        mini = min(mini, total);
    }
    cout << mini;
}

Submission Info

Compile Error

./Main.cpp: In function 'void permutations(std::vector<std::vector<long long int> >&, std::vector<long long int>, ll)':
./Main.cpp:36:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if (idx == arr.size())
      |         ~~~~^~~~~~~~~~~~~
./Main.cpp:41:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (ll i = idx; i < arr.size(); i++)
      |                      ~~^~~~~~~~~~~~

Judge Result