oj.uz

Submission #796579

# Submission time Handle Problem Language Result Execution time Memory
796579 2023-07-28T14:16:14 Z AbdullahMohammedAhmad Minerals (JOI19_minerals) C++14
75 / 100
 89 ms 9800 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 4 ms 976 KB Output is correct
4 Correct 9 ms 1616 KB Output is correct
5 Correct 18 ms 2752 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct
19 Correct 84 ms 9800 KB Output is correct
20 Correct 81 ms 9748 KB Output is correct
21 Correct 86 ms 9752 KB Output is correct
22 Correct 83 ms 9572 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct
19 Correct 84 ms 9800 KB Output is correct
20 Correct 81 ms 9748 KB Output is correct
21 Correct 86 ms 9752 KB Output is correct
22 Correct 83 ms 9572 KB Output is correct
23 Incorrect 80 ms 9544 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct
19 Correct 84 ms 9800 KB Output is correct
20 Correct 81 ms 9748 KB Output is correct
21 Correct 86 ms 9752 KB Output is correct
22 Correct 83 ms 9572 KB Output is correct
23 Incorrect 80 ms 9544 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct
19 Correct 84 ms 9800 KB Output is correct
20 Correct 81 ms 9748 KB Output is correct
21 Correct 86 ms 9752 KB Output is correct
22 Correct 83 ms 9572 KB Output is correct
23 Incorrect 80 ms 9544 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 9 ms 1616 KB Output is correct
9 Correct 18 ms 2752 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 18 ms 2608 KB Output is correct
12 Correct 19 ms 2844 KB Output is correct
13 Correct 23 ms 2796 KB Output is correct
14 Correct 19 ms 2752 KB Output is correct
15 Correct 83 ms 9756 KB Output is correct
16 Correct 89 ms 9692 KB Output is correct
17 Correct 83 ms 9704 KB Output is correct
18 Correct 78 ms 9520 KB Output is correct
19 Correct 84 ms 9800 KB Output is correct
20 Correct 81 ms 9748 KB Output is correct
21 Correct 86 ms 9752 KB Output is correct
22 Correct 83 ms 9572 KB Output is correct
23 Incorrect 80 ms 9544 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -