Submission #206686

#TimeUsernameProblemLanguageResultExecution timeMemory
206686opukittpceno_hhrRope (JOI17_rope)C++17
0 / 100
1401 ms504 KiB
#ifndef LOCAL #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #endif #include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <random> #include <functional> using namespace std; const int N = 15; int dp[N][N + 1]; int sdp[N + 1]; int pdp[N + 1]; int ts[N]; int s[N + 1]; int can(int i, int len) { if (len % 2 == 1) { return 0; } if (len == 0) { return 1; } if (dp[i][len] == -1) { dp[i][len] = can(i + 1, len - 2) & ((ts[i] == ts[i + len - 1])); } return dp[i][len]; } void ref() { for (int i = 0; i < N; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = -1; } } } int cans(int n) { ref(); fill(pdp, pdp + N + 1, 0); fill(sdp, sdp + N + 1, 0); pdp[0] = 1; sdp[0] = 1; for (int i = 0; i < n; i++) { for (int len = 2; i + len <= n; len++) { pdp[i + len / 2] |= (pdp[i] & can(i, len)); } } reverse(ts, ts + n); ref(); for (int i = 0; i < n; i++) { for (int len = 2; i + len <= n; len++) { sdp[i + len / 2] |= (sdp[i] & can(i, len)); } } for (int i = 0; i <= n; i++) { if (n - 2 - i >= 0 && pdp[i] && sdp[n - 2 - i]) { // cout << "NO\n"; // for (int i = 0; i < n; i++) { // cout << ts[i] << ' '; // } // cout << endl; return 1; } } // cout << "NO\n"; // for (int i = 0; i < n; i++) { // cout << ts[i] << ' '; // } // cout << endl; return 0; } int solve(int n, int a, int b) { int ans = n; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if ((i >> j) & 1) { ts[j] = a; } else { ts[j] = b; } } if (cans(n)) { int c = 0; for (int j = 0; j < n; j++) { c += (s[j] != ts[j]); } ans = min(ans, c); } } return ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> s[i]; s[i]--; } vector<int> ans(m, n); for (int i = 0; i < m; i++) { for (int j = i + 1; j < m; j++) { int v = solve(n, i, j); ans[i] = min(ans[i], v); ans[j] = min(ans[j], v); } } for (auto t : ans) { cout << t << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...