fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 51;
  7. int n, m;
  8. string s;
  9. struct query {
  10.     int l, r, x, k;
  11. };
  12. query q[N];
  13. namespace sub1 {
  14. // 0 (chưa điền được gì), 1 (là 0), 2 (1) 3( đa giá trị);
  15. int a[N];
  16. int b[N];
  17. bool check(int msk) {
  18.     for (int i = 0; i < n; i++) b[i] = msk >> i & 1;
  19.     for (int i = 0; i < n; i++) if (s[i] != '?') {
  20.         if (s[i] == '1' && b[i] != 1) return 0;
  21.         if (s[i] == '0' && b[i] != 0) return 0;
  22.     }
  23.     for (int i = 1; i <= m; i++) {
  24.         int l = q[i].l - 1, r = q[i].r - 1, x = q[i].x, k = q[i].k;
  25.  
  26.         int cnt = 0, mmax = 0;
  27.         for (int j = l; j <= r; j++) {
  28.             if (b[j] == x) cnt++;
  29.             else cnt = 0;
  30.             mmax = max(mmax, cnt);
  31.         }
  32.         // cerr << "CHECK: " << msk << ": "; for (int i = 0; i < n; i++) cerr << b[i] << " "; cerr << "\n";
  33.         // cerr << "WITH " << l << " " << r << " " << x << " " << k << " | " << cnt << " " << mmax << '\n';
  34.         if (mmax < k) return 0;
  35.     }
  36.  
  37.     return 1;
  38. }
  39. void solve() {
  40.     bool ok = 0;
  41.     for (int msk = 0; msk < (1 << n); msk++) {
  42.         if (!check(msk)) continue;
  43.         ok = 1;
  44.         // cerr << "ok heheheh: " << msk << ": "; for (int i = 0; i < n; i++) cerr << b[i] << " "; cerr << "\n";
  45.         for (int i = 0; i < n; i++) if (s[i] == '?') {
  46.             int x = b[i] + 1;
  47.             a[i] |= x;
  48.             // cerr << a[i] << " ";
  49.         }
  50.         // cerr << "\n";
  51.     }
  52.     if (!ok) return cout <<-1, void();
  53.     for (int i = 0; i < n; i++) {
  54.         if (s[i] == '?') {
  55.             if (a[i] == 3) cout << '?';
  56.             else cout <<a[i] - 1;
  57.         }
  58.         else cout << s[i];
  59.     }
  60. }
  61. };
  62.  
  63.  
  64. namespace sub2 {
  65. vector<int> pos;
  66. // 0 (chưa điền được gì), 1 (là 0), 2 (1) 3( đa giá trị);
  67. int a[N], b[N], sz;
  68.  
  69. bool checksub() {
  70.     for (int i = 0; i < n; i++) {
  71.         if (s[i] == '?') pos.push_back(i);
  72.     }
  73.     return (int)pos.size() <= 15;
  74. }
  75. bool check(int msk) {
  76.     for (int i = 0; i < sz; i++) b[pos[i]] = msk >> i & 1;
  77.  
  78.     for (int i = 1; i <= m; i++) {
  79.         int l = q[i].l - 1, r = q[i].r - 1, x = q[i].x, k = q[i].k;
  80.  
  81.         int cnt = 0, mmax = 0;
  82.         for (int j = l; j <= r; j++) {
  83.             if (b[j] == x) cnt++;
  84.             else cnt = 0;
  85.             mmax = max(mmax, cnt);
  86.         }
  87.         // cerr << "CHECK: " << msk << ": "; for (int i = 0; i < n; i++) cerr << b[i] << " "; cerr << "\n";
  88.         // cerr << "WITH " << l << " " << r << " " << x << " " << k << " | " << cnt << " " << mmax << '\n';
  89.         if (mmax < k) return 0;
  90.     }
  91.  
  92.     return 1;
  93. }
  94.  
  95. void solve() {
  96.     sz = pos.size();
  97.  
  98.     for (int i = 0; i < n; i++) {
  99.         if (s[i] != '?') b[i] = a[i] = (s[i] - '0');
  100.  
  101.     }
  102.     bool ok = 0;
  103.     for (int msk = 0; msk < (1 << sz); msk++) {
  104.         if (!check(msk)) continue;
  105.         ok = 1;
  106.         // cerr << "ok heheheh: " << msk << ": "; for (int i = 0; i < n; i++) cerr << b[i] << " "; cerr << "\n";
  107.         for (int i = 0; i < sz; i++) {
  108.             int x = b[pos[i]] + 1;
  109.             a[pos[i]] |= x;
  110.             // cerr << a[i] << " ";
  111.         }
  112.         // cerr << "\n";
  113.     }
  114.     if (!ok) return cout <<-1, void();
  115.     for (int i = 0; i < n; i++) {
  116.         if (s[i] == '?') {
  117.             if (a[i] == 3) cout << '?';
  118.             else cout <<a[i] - 1;
  119.         }
  120.         else cout << s[i];
  121.     }
  122. }
  123. };
  124.  
  125. namespace sub3 {
  126. bool checksub() {
  127.     for (int i = 1; i <= m; i++) if (q[i].k != 1) return 0;
  128.     return 1;
  129. }
  130. int a[N]; //0 (0), 1 (là 1), 2 (chưa điền gì)
  131. bool delQ[N];
  132. int calc(int l, int r, int x) {
  133.     int cnt = 0;
  134.     for (int j = l; j <= r; j++) {
  135.         if (a[j] == x) return 2;
  136.         else if (a[j] == 2) cnt++;
  137.     }
  138.     return cnt;
  139. }
  140. void solve() {
  141.     for (int i = 0; i < n; i++) {
  142.         if (s[i] == '?') a[i] = 2;
  143.         else a[i] = (s[i] - '0');
  144.     }
  145.     while(1) {
  146.         int change = 0;
  147.         for (int i = 1; i <= m; i++) if (!delQ[i]) {
  148.             // if (q[i].k == 0) continue;
  149.             int cnt = calc(q[i].l - 1, q[i].r - 1, q[i].x);
  150.             if (cnt == 0) return cout << -1, void();
  151.             if (cnt == 1) {
  152.                 change = i;
  153.                 delQ[i] = 1;
  154.                 break;
  155.             }
  156.         }
  157.         if (!change) break;
  158.         for (int i = q[change].l - 1; i <= q[change].r - 1; i++) if (a[i] == 2) {
  159.             a[i] = q[change].x;
  160.             break;
  161.         }
  162.     }
  163.  
  164.     for (int i = 0; i < n; i++) {
  165.         if (a[i] == 2) cout << '?';
  166.         else cout <<a[i];
  167.     }
  168. }
  169. };
  170.  
  171. using pii = pair<int, int>;
  172. namespace sub4 {
  173. bool checksub() {
  174.     int tar = q[1].x;
  175.     for (int i = 1; i <= m; i++) if (q[i].x != tar) return 0;
  176.     return 1;
  177. }
  178. int a[N]; //0 (0), 1 (là 1), 2 (chưa điền gì)
  179. bool delQ[N];
  180. int ps[N];
  181. pii calc(int l, int r, int x, int k) {
  182.     ps[l - 1] = 0;
  183.     for (int i = l; i <= r; i++) {
  184.         ps[i] = ps[i - 1];
  185.         if (a[i] == x || a[i] == 2) ps[i]++;
  186.     }
  187.     int L = -1, R = n;
  188.     for (int i = l + k - 1; i <= r; i++) {
  189.         int j = i - k + 1;
  190.         if (ps[i] - ps[j - 1] == k) {
  191.             L = max(L, j);
  192.             R = min(R, i);
  193.         }
  194.     }
  195.     return {L, R};
  196. }
  197. void solve() {
  198.     for (int i = 0; i < n; i++) {
  199.         if (s[i] == '?') a[i] = 2;
  200.         else a[i] = (s[i] - '0');
  201.     }
  202.     while(1) {
  203.         bool change = 0;
  204.         for (int i = 1; i <= m; i++) if (!delQ[i]) {
  205.             // if (q[i].k == 0) continue;
  206.             pii item = calc(q[i].l - 1, q[i].r - 1, q[i].x, q[i].k);
  207.             int L = item.ft, R = item.sc;
  208.             if (L == -1 || R == n) return cout << -1, void();
  209.             if (L <= R) {
  210.                 change = 1;
  211.                 for (int j = L; j <= R; j++) a[j] = q[i].x;
  212.                 delQ[i] = 1;
  213.                 break;
  214.             }
  215.         }
  216.         if (!change) break;
  217.     }
  218.  
  219.     for (int i = 0; i < n; i++) {
  220.         if (a[i] == 2) cout << '?';
  221.         else cout <<a[i];
  222.     }
  223. }
  224. };
  225.  
  226. namespace subCan {
  227. int a[N]; //0 (0), 1 (là 1), 2 (chưa điền gì)
  228. bool delQ[N];
  229. int ps[N];
  230. pii calc(int l, int r, int x, int k) {
  231.     ps[l - 1] = 0;
  232.     for (int i = l; i <= r; i++) {
  233.         ps[i] = ps[i - 1];
  234.         if (a[i] == x || a[i] == 2) ps[i]++;
  235.     }
  236.     int L = -1, R = n;
  237.     for (int i = l + k - 1; i <= r; i++) {
  238.         int j = i - k + 1;
  239.         if (ps[i] - ps[j - 1] == k) {
  240.             L = max(L, j);
  241.             R = min(R, i);
  242.         }
  243.     }
  244.     return {L, R};
  245. }
  246. void solve() {
  247.     for (int i = 0; i < n; i++) {
  248.         if (s[i] == '?') a[i] = 2;
  249.         else a[i] = (s[i] - '0');
  250.     }
  251.     while(clock() < 0.8 * CLOCKS_PER_SEC) {
  252.         while(1) {
  253.             bool change = 0;
  254.             for (int i = 1; i <= m; i++) if (!delQ[i]) {
  255.                 // if (q[i].k == 0) continue;
  256.                 pii item = calc(q[i].l - 1, q[i].r - 1, q[i].x, q[i].k);
  257.                 int L = item.ft, R = item.sc;
  258.                 if (L == -1 || R == n) return cout << -1, void();
  259.                 if (L <= R) {
  260.                     change = 1;
  261.                     for (int j = L; j <= R; j++) a[j] = q[i].x;
  262.                     delQ[i] = 1;
  263.                     break;
  264.                 }
  265.             }
  266.             if (!change) break;
  267.         }
  268.         for (int i = 1; i <= m; i++) delQ[i] = 0;
  269.     }
  270.     for (int i = 0; i < n; i++) {
  271.         if (a[i] == 2) cout << '?';
  272.         else cout <<a[i];
  273.     }
  274. }
  275. };
  276.  
  277. signed main() {
  278.     cin.tie(NULL)->sync_with_stdio(false);
  279.     if(ifstream("MAKHOA.inp")) {
  280.         freopen("MAKHOA.inp", "r", stdin);
  281.         freopen("MAKHOA.out", "w", stdout);
  282.     }
  283.     cin >> n >> m >> s;
  284.     for (int i = 1; i <= m; i++) cin >> q[i].k >> q[i].x >> q[i].l >> q[i].r;
  285.     // if (n <= 15) return sub1::solve(), 0;
  286.     // if (sub2::checksub()) return sub2::solve(), 0;
  287.     // if (sub3::checksub()) return sub3::solve(), 0;
  288.     // if (sub4::checksub()) return sub4::solve(), 0;
  289.     return subCan::solve(), 0;
  290.     cout << -1;
  291.     return 0;
  292. }
Success #stdin #stdout 0.8s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/REFleL
language:
C++14 (gcc 8.3)
created:
13 days 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!