Submission #796579

#	Time	Username	Problem	Language	Result	Execution time	Memory
796579		AbdullahMohammedAhmad	Minerals (JOI19_minerals)	C++14	75 / 100	89 ms	9800 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

int common[18][18];
int cost[18][18];
int have[18];
int nodes;

int dp[18][1<<19];
int par[18][1<<19];

int tsp(int i, int mask)
{
    if(mask == (1<<i))
    {
        return 0;
    }
    if(dp[i][mask] != 0)
    {
        return dp[i][mask];
    }
    int res = INT_MAX;
    for(int j = 0; j < nodes; j++)
    {
        if((mask&(1<<j)) && j != i)
        {
            int now = tsp(j, mask&(~(1<<i)))+cost[j][i];
            if(now < res)
            {
                res = now;
                par[i][mask] = j;
            }
        }
    }
    return dp[i][mask] = res;
}

vector<int> get_best_order(int n)
{
    nodes = ceil(log2(n));
    for(int i = 0; i < nodes; i++) {
        for(int k = 0; k < n; k++)
        {
            if((k&(1<<i)))
            {
                have[i]++;
            }
        }
        for(int j = i+1; j < nodes; j++)
        {
            for(int k = 0; k < n; k++)
            {
                if(((k>>i)^(k>>j))&1)
                {
                    cost[i][j]++;
                    cost[j][i]++;
                }
            }
        }
    }
    int ans = INT_MAX;
    int idx = -1;
    for(int i = 0; i < nodes; i++)
    {
        tsp(i, (1<<nodes)-1);
        if(dp[i][(1<<nodes)-1]+n-have[i] < ans)
        {
            ans = dp[i][(1<<nodes)-1]+n-have[i];
            idx = i;
        }
    }
    assert(idx != -1);
    vector<int> path;
    path.push_back(idx);
    int msk = (1<<nodes)-1;
    while(true)
    {
        if(msk == (1<<idx))
        {
            break;
        }
        
        int nxt = par[idx][msk];
        msk^=(1<<idx);
        idx = nxt;
        path.push_back(idx);
    }
    //reverse(path.begin(), path.end());
    return path;
}

mt19937 rng(66);
void Solve(int n) {
    vector<int> p1, p2;
    int ans = 0, prevans = -1;
    vector<int> bulanea(2 * n);
    iota(bulanea.begin(), bulanea.end(), 1);
    shuffle(bulanea.begin(), bulanea.end(), rng);
    for(int i: bulanea) {
        ans = Query(i);
        if(ans == prevans) {
            p2.push_back(i);
        } else {
            p1.push_back(i);
        }
        prevans = ans;
    }
    assert(p1.size() == n && p2.size() == n);
    vector<int> pr(n, 0);
    vector<bool> bagat(n, 1);
    vector<int> best_order = get_best_order(n);
    
    for(int bit: best_order) {
        int cntt = 0;
        for(int i = 0; i < n; ++i) {
            if(i >> bit & 1) {
                ++cntt;
                if(!bagat[i]) prevans = Query(p1[i]);
                bagat[i] = 1;
            } else {
                if(bagat[i]) prevans = Query(p1[i]);
                bagat[i] = 0;
            }
        }
        for(int i = 0; i < n && cntt; ++i) {
            if(pr[i] + (1 << bit) >= n) continue;
            int ans = Query(p2[i]);
            if(ans == prevans) {
                pr[i] += (1 << bit);
                --cntt;
            }
            prevans = ans;
        }
    }
    for(int i = 0; i < n; ++i) {
        Answer(p2[i], p1[pr[i]]);
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minerals.cpp:2:
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:109:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     assert(p1.size() == n && p2.size() == n);
      |            ~~~~~~~~~~^~~~
minerals.cpp:109:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     assert(p1.size() == n && p2.size() == n);
      |                              ~~~~~~~~~~^~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10