Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // #include <ext/pb_ds/assoc_container.hpp>
  3. // #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. #define rep(i, a, n) for(ll i = (a); i < (n); i++)
  8. #define per(i, a, n) for(ll i = (n-1); i >= (a); i--)
  9. #define F first
  10. #define S second
  11. #define maxx(a, b) a = max(a, b)
  12. #define minn(a, b) a = min(a, b)
  13. #define db(x) cerr << #x << " = " << x << endl
  14. #define N 1111111
  15. #define mod 1000000007
  16. #define rt return
  17. #define inf 123456789123456789ll
  18.  
  19. using namespace std;
  20. // using namespace __gnu_pbds;
  21.  
  22. // typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
  23.  
  24. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  25.  
  26. void err(istream_iterator<string> it) {}
  27. template<typename T, typename... Args>
  28. void err(istream_iterator<string> it, T a, Args... args)
  29. {
  30. cerr << *it << " = " << a << endl;
  31. err(++it, args...);
  32. }
  33.  
  34. ll rec(ll n, ll k, ll t, ll son)
  35. {
  36. ll ok = 0;
  37.  
  38. // if(t)ok = 1;
  39.  
  40. rep(i,0,n-k+1)
  41. {
  42. ll now = son;
  43. ll okmi = 1;
  44.  
  45. rep(j,i,i+k)
  46. if(now&(1ll<<j))
  47. {
  48. okmi = 0;
  49. break;
  50. }
  51. else
  52. now |= (1ll<<j);
  53. if(!okmi)
  54. continue;
  55. ok |= !rec(n,k,t^1,now);
  56. }
  57. // error(t,ok);
  58. rt ok;
  59. }
  60.  
  61. int main()
  62. {
  63. ios_base::sync_with_stdio(0);
  64. cin.tie(0);
  65. cout.tie(0);
  66.  
  67. ll n,k; cin>>n>>k;
  68.  
  69. string s; cin>>s;
  70.  
  71. if(k == 1ll)
  72. {
  73. ll now = count(begin(s),end(s),'O');
  74. cout<<(now&1ll ? 1ll : 2ll);
  75. rt 0;
  76. }
  77.  
  78. bool ok = 0;
  79.  
  80. ll son = 0ll;
  81.  
  82. rep(i,0,n)
  83. son |= (s[i] == 'X' ? (1ll<<i) : 0ll);
  84. //
  85. // db(son);
  86.  
  87. ll ans = 0;
  88.  
  89. rep(i,0,n-k+1)
  90. {
  91. ll now = son;
  92. ll okmi = 1;
  93. rep(j,i,i+k)
  94. if(now&(1ll<<j))
  95. {
  96. okmi = 0;
  97. break;
  98. }
  99. else
  100. now |= (1ll<<j);
  101. if(!okmi)
  102. continue;
  103. ok = 1;
  104. ans |= !rec(n,k,1,now);
  105. }
  106.  
  107. if(!ok)
  108. rt cout<<0,0;
  109.  
  110. cout<<(ans ? 1 : 2);
  111.  
  112. rt 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement