Submission #1013553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013553		amine_aroua	Netrpeljivost (COI23_netrpeljivost)	C++17	10 / 100	1157 ms	524288 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
int main()
{
    int n ;
    cin>>n;
    vector<vector<int>> mat(n , vector<int>(n));
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            cin>>mat[i][j];
        }
    }
    vector<int> beg ;
    for(int i = 0 ; i < n; i++)
        beg.pb(i);
    vector<vector<int>> states;
    queue<vector<int>> q;
    q.push(beg);
    map<vector<int> , int> vis;
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        if(vis[cur])
            continue;
        states.pb(cur);
        vis[cur] = 1;
        for(int p = 1 ; p < n ; p*=2)
        {
            for(int i = 0 ; i * p < n ; i+=2)
            {
                vector<int> new_cur = cur;
                for(int j = i * p ; j < (i + 1) * p ; j++)
                    swap(new_cur[j] , new_cur[j + p]);
                if(!vis[new_cur])
                    q.push(new_cur);
            }
        }
    }
    intt ans = LLONG_MAX;
//    for(auto state : states)
//    {
//        cout<<'\n';
//        for(auto x : state)
//            cout<<x<<" ";
//        cout<<'\n';
//    }
    for(auto state : states)
    {
        intt cur = 0;
        for(int i =0 ; i + 1 < n ; i++)
        {
            cur+= mat[state[i]][state[i + 1]];
        }
        ans = min(ans , cur);
    }
    cout<<ans<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 17
• Subtask 3: 0 / 32
• Subtask 4: 0 / 41