fork download
  1. /*********** [ scopeInfinity ] ******************/
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef std::vector<ll> vll;
  9. typedef std::vector<pair<int,int> > vpi;
  10. typedef std::vector<pair<ll,ll> > vpl;
  11. typedef std::vector<int> vi;
  12.  
  13. ll MOD = 1e9+7;
  14. ll PRIME = 999727999;
  15. ll PRIME2 = 999999937;
  16. ll INF = LLONG_MAX/4;
  17.  
  18. #define forv(it,m) for (auto it = (m).begin(); it != (m).end(); ++it)
  19. #define rep(i,n) for (int i=0;i<(int)(n);i++)
  20. #define repr(i,n) for (int i=(int)(n)-1;i>=0;i--)
  21. #define all(v) v.begin(),v.end()
  22. #define endl '\n'
  23. #define mp make_pair
  24. #define pb(x) push_back((x))
  25. #define what_is(x) cerr << #x << " is " << (x) << endl;
  26. #define NEW(x,n) {(x).clear();(x).resize((n));}
  27. #define xx first
  28. #define yy second
  29.  
  30. template <class F1,class F2> ostream& operator<<(ostream& os, const pair<F1,F2>& p) {
  31. return os<<p.xx<<' '<<p.yy; }
  32. template <class F1,class F2> istream& operator>>(istream& is, pair<F1,F2>& p) {
  33. return is>>p.xx>>p.yy; }
  34. template <class F> ostream& operator<<(ostream& os, const std::vector<F>& v) {
  35. rep(i,v.size()) os<<v[i]<<" "; return os; }
  36. template <class F> istream& operator>>(istream& is, std::vector<F> &v) {
  37. rep(i,v.size()) is>>v[i]; return is; }
  38.  
  39. vector<string> split(const std::string &s, char delim) {
  40. vector<string> e; stringstream ss(s);string item;
  41. while(getline(ss, item, delim)) e.push_back(item);
  42. return e;
  43. }
  44.  
  45. ll Pow(ll a ,ll b ,ll Mo){
  46. ll ans = 1;
  47. for (; b; b >>= 1, a = a * a % Mo) if (b&1) ans = ans * a % Mo;
  48. return ans;
  49. }
  50. ll _div(ll a,ll b) { return (a*Pow(b,MOD-2,MOD))%MOD; }
  51. ll nCr(ll n,ll r) {
  52. static ll MAXF = 1e6;static std::vector<ll> fact(MAXF,1);
  53. for (int i = 1; i < MAXF; ++i) fact[i]=(fact[i-1]*i)%MOD;
  54. MAXF=0; return (fact[n]*Pow((fact[r]*fact[n-r])%MOD,MOD-2,MOD))%MOD;
  55. }
  56.  
  57. vector<int> Zfunc(string &s) {
  58. int n=s.length();
  59. vector<int> z(n,0);
  60. for(int i=1,l=0,r=0;i<n;i++) {
  61. if(i<=r) z[i] = min(z[i-l],r-i+1);
  62. while(i+z[i]<n && s[i+z[i]]==s[z[i]]) z[i]++;
  63. if(r<i+z[i]-1)l=i,r=i+z[i]-1;
  64. }
  65. return z;
  66. }
  67.  
  68. ll n,m,p;
  69. std::set<string> avoid;
  70.  
  71. std::vector<ll> costOn1, costOn0;
  72. std::vector<ll> changeCost;
  73. std::vector<char> toChange;
  74.  
  75.  
  76. pair<ll,string> obtainFromIndex(string &a,std::vector<int> &index,ll cost) {
  77. string ss = a;
  78. ll mc = cost;
  79. for (int i = 0; i < p; ++i)
  80. if(index[i]) {
  81. ss[i]=toChange[i];
  82. mc += changeCost[i];
  83. }
  84. return mp(mc,ss);
  85. }
  86.  
  87. ll solve() {
  88. cin>>n>>m>>p;
  89. avoid.clear();
  90. std::vector<string> v(n);
  91. cin>>v;
  92. costOn1=std::vector<ll> (p,0);
  93. costOn0=std::vector<ll> (p,0);
  94. changeCost=std::vector<ll>(p,0);
  95. toChange=std::vector<char>(p,' ');
  96.  
  97. for (int i = 0; i < n; ++i)
  98. {
  99. for (int j = 0; j < p; ++j)
  100. {
  101. if(v[i][j]=='1')
  102. costOn0[j]++;
  103. else
  104. costOn1[j]++;
  105. }
  106. }
  107.  
  108.  
  109. for (int i = 0; i < m; ++i)
  110. {
  111. string s;
  112. cin>>s;
  113. avoid.insert(s);
  114. }
  115. string a="";
  116. ll cost = 0;
  117. for (int i = 0; i < p; ++i)
  118. {
  119. if(costOn0[i]<costOn1[i]) {
  120. a+='0';
  121. toChange[i]= '1';
  122. } else {
  123. a+='1';
  124. toChange[i]='0';
  125. }
  126. cost += min(costOn0[i],costOn1[i]);
  127. changeCost[i]= max(costOn0[i],costOn1[i])- min(costOn0[i],costOn1[i]);
  128. }
  129.  
  130. priority_queue<pair<ll, std::vector<int> > > pq;
  131. pq.push(mp(-cost,std::vector<int>(p,0)));
  132. set<std::vector<int> > indexDone;
  133. while(!pq.empty()) {
  134.  
  135. std::vector<int> index=pq.top().second;
  136. pq.pop();
  137. if(indexDone.count(index))
  138. continue;
  139. indexDone.insert(index);
  140. auto mcss = obtainFromIndex(a, index, cost);
  141. if(avoid.count(mcss.yy) == 0)
  142. return mcss.xx;
  143.  
  144. for (int i = 0; i < p; ++i)
  145. if(index[i]==0) {
  146. std::vector<int> newIndex=index;
  147. newIndex[i]=1;
  148. auto newMCSS = obtainFromIndex(a,newIndex, cost);
  149. assert(mcss.xx <= newMCSS.xx);
  150. pq.push(mp(-newMCSS.xx, newIndex));
  151. // cerr<<newMCSS<<" pushed\n";
  152. }
  153. }
  154.  
  155. assert(0);
  156. }
  157.  
  158. int main(int argc, char const *argv[])
  159. {
  160. std::ios::sync_with_stdio(false);cin.tie(0);
  161. // cout<<fixed<<setprecision(1);
  162.  
  163.  
  164. int T;
  165. cin>>T;
  166. for (int i = 0; i < T; ++i)
  167. {
  168. cout<<"Case #"<<i+1<<": ";
  169. cout<<solve();
  170. cout<<endl;
  171. }
  172.  
  173.  
  174. return 0;
  175. }
  176.  
  177.  
Success #stdin #stdout 0s 15248KB
stdin
2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101
stdout
Case #1: 4
Case #2: 2