fork download
copy 
  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
comments (?)
stdin
copy 
2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101
stdout
copy 
Case #1: 4
Case #2: 2
https://ideone.com/VpVlbt
language:
C++14 (gcc 8.3)
created:
6 years 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!