fork download
copy 
  1. // Author: 4uckd3v - Nguyen Cao Duc
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int MAX_N = 1e6;
  8. const int MOD = 1e9 + 7;
  9.  
  10. int n, q, x, y, startMask;
  11. int c[15], Pow[15], a[15];
  12. int dp[MAX_N + 5];
  13.  
  14. int prv(int c) {
  15.     return (c - 1 + 3) % 3;
  16. };
  17.  
  18. int nxt(int c) {
  19.     return (c + 1) % 3;
  20. };
  21.  
  22. int DP(int mask, int l, int r) {
  23.     if (dp[mask] != -1) return dp[mask];
  24.     if (mask == startMask) return 0;
  25.  
  26.     int& ret = dp[mask] = 1e9;
  27.  
  28.     for (int i = l; i <= r; i++) {
  29.         for (int j = l; j <= r; j++) {
  30.             if (i == j) continue;
  31.             int oldI = c[i], oldJ = c[j];
  32.  
  33.             int newMask = mask;
  34.             newMask -= Pow[i - l] * oldI;
  35.             newMask -= Pow[j - l] * oldJ;
  36.  
  37.             c[i] = prv(c[i]);
  38.             c[j] = nxt(c[j]);
  39.  
  40.             newMask += Pow[i - l] * c[i];
  41.             newMask += Pow[j - l] * c[j];
  42.  
  43.             ret = min(ret, DP(newMask, l, r) + 1);
  44.  
  45.             c[i] = oldI, c[j] = oldJ;
  46.         }
  47.     }
  48.  
  49.     return ret;
  50. };
  51.  
  52. int main() {
  53.     ios_base::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     if (fopen("MAIN.INP", "r")) {
  56.         freopen("MAIN.INP", "r", stdin);
  57.         freopen("MAIN.OUT", "w", stdout);
  58.     };
  59.  
  60.     cin >> n >> q >> x >> y;
  61.  
  62.     for (int i = 1; i <= n; i++) cin >> a[i];
  63.  
  64.     Pow[0] = 1;
  65.     for (int i = 1; i <= n; i++) Pow[i] = Pow[i - 1] * 3;
  66.  
  67.     while (q--) {
  68.         int l, r;
  69.         cin >> l >> r;
  70.  
  71.         startMask = 0;
  72.         for (int i = l; i <= r; i++) startMask += Pow[i - l] * a[i], c[i] = 0;
  73.  
  74.         memset(dp, -1, sizeof dp);
  75.  
  76.         cout << (DP(0, l, r) == 1e9 ? -1 : DP(0, l, r)) << '\n';
  77.     }
  78. };
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CNSVyV
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!