Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
307
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int MOD = 1e9+7;
  9. const int MAX = 5e3 + 10;
  10.  
  11. int dp[MAX][MAX], last_w[MAX], last_l[MAX], tw[MAX], tl[MAX];
  12. bool goat[MAX];
  13.  
  14. int main() {
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0);
  17.  
  18.     #ifdef LOCAL
  19.         freopen("input.txt", "r", stdin);
  20.         freopen("output.txt", "w", stdout);
  21.     #else
  22.         #define endl '\n'
  23.     #endif // LOCAL
  24.  
  25.     int n, m, k; cin >> n >> m >> k;
  26.     for(int i = 0; i < n; i++)
  27.         cin >> goat[i];
  28.  
  29.     memset(dp, -1, sizeof dp);
  30.  
  31.     for(int i = 0; i < n; i++) {
  32.         dp[i][m-1] = 0;
  33.         last_l[i] = last_w[i] = INT_MAX;
  34.         if(dp[i][m-1] == 0) last_l[i] = m-1;
  35.         else last_w[i] = m-1;
  36.     }
  37.     for(int j = m-2; j >= 0; j--) {
  38.  
  39.         memcpy(tl, last_l, sizeof last_l);
  40.         memcpy(tw, last_w, sizeof last_w);
  41.  
  42.         for(int i = 0; i < n; i++) {
  43.             int nxt = (i+1)%n;
  44.             if(goat[nxt] == goat[i]) { /// I can win if find some winner
  45.                 if(j + k >= last_w[nxt])
  46.                     dp[i][j] = 1;
  47.                 else
  48.                     dp[i][j] = 0;
  49.             } else { /// I can win if find some looser
  50.                 if(j + k >= last_l[nxt])
  51.                     dp[i][j] = 1;
  52.                 else
  53.                     dp[i][j] = 0;
  54.             }
  55.             if(dp[i][j] == 0) tl[i] = j;
  56.             else tw[i] = j;
  57.         }
  58.  
  59.         memcpy(last_l, tl, sizeof last_l);
  60.         memcpy(last_w, tw, sizeof last_w);
  61.     }
  62.  
  63.     for(int i = 0; i < n; i++) {
  64.         if(i) cout << " ";
  65.         if(dp[i][0] == 1) cout << goat[i];
  66.         else cout << !goat[i];
  67.  
  68.     }
  69.     cout << endl;
  70.  
  71.  
  72.  
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement