oj.uz

Submission #700912

# Submission time Handle Problem Language Result Execution time Memory
700912 2023-02-19T12:03:19 Z bebra Group Photo (JOI21_ho_t3) C++17
12 / 100
 1189 ms 82516 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 20;
const int MAX_MASK = 1 << MAX_N;
int dp[MAX_MASK][MAX_N];
const int INF = 1e9;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
        pos[a[i]] = i;
    }

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            if (!(mask & (1 << i))) continue;
            int cnt = __builtin_popcount(mask);
            if (cnt == 1) {
                dp[mask][i] = pos[i];
                break;
            }
            int cnt_less = 0;
            for (int j = 0; j < n; ++j) {
                if ((mask & (1 << j)) && (pos[j] > pos[i])) {
                    ++cnt_less;
                }
            }
            int swaps_n = abs((cnt - 1) - (pos[i] + cnt_less));
            dp[mask][i] = INF;
            for (int j = 0; j < i + 2; ++j) {
                if (i == j) continue;
                if (!(mask & (1 << j))) continue;
                dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + swaps_n);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    cout << ans << '\n';
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 262 ms 20812 KB Output is correct
12 Correct 531 ms 41236 KB Output is correct
13 Correct 563 ms 41508 KB Output is correct
14 Correct 1188 ms 82332 KB Output is correct
15 Correct 1149 ms 82348 KB Output is correct
16 Correct 1149 ms 82388 KB Output is correct
17 Correct 1144 ms 82516 KB Output is correct
18 Correct 1176 ms 82360 KB Output is correct
19 Correct 1189 ms 82348 KB Output is correct
20 Correct 1123 ms 82272 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 262 ms 20812 KB Output is correct
12 Correct 531 ms 41236 KB Output is correct
13 Correct 563 ms 41508 KB Output is correct
14 Correct 1188 ms 82332 KB Output is correct
15 Correct 1149 ms 82348 KB Output is correct
16 Correct 1149 ms 82388 KB Output is correct
17 Correct 1144 ms 82516 KB Output is correct
18 Correct 1176 ms 82360 KB Output is correct
19 Correct 1189 ms 82348 KB Output is correct
20 Correct 1123 ms 82272 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 262 ms 20812 KB Output is correct
12 Correct 531 ms 41236 KB Output is correct
13 Correct 563 ms 41508 KB Output is correct
14 Correct 1188 ms 82332 KB Output is correct
15 Correct 1149 ms 82348 KB Output is correct
16 Correct 1149 ms 82388 KB Output is correct
17 Correct 1144 ms 82516 KB Output is correct
18 Correct 1176 ms 82360 KB Output is correct
19 Correct 1189 ms 82348 KB Output is correct
20 Correct 1123 ms 82272 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 262 ms 20812 KB Output is correct
12 Correct 531 ms 41236 KB Output is correct
13 Correct 563 ms 41508 KB Output is correct
14 Correct 1188 ms 82332 KB Output is correct
15 Correct 1149 ms 82348 KB Output is correct
16 Correct 1149 ms 82388 KB Output is correct
17 Correct 1144 ms 82516 KB Output is correct
18 Correct 1176 ms 82360 KB Output is correct
19 Correct 1189 ms 82348 KB Output is correct
20 Correct 1123 ms 82272 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -