fork download
copy 
  1. /*
  2.  *    J1K7_7
  3.  *
  4.  *    You can use my contents on a Creative Commons - Attribution 4.0 International - CC BY 4.0 License.  XD 
  5.  *    - JASKAMAL KAINTH
  6.  */
  7. #include <iostream>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <string>
  11. #include <vector>
  12. #include <deque>
  13. #include <queue>
  14. #include <stack>
  15. #include <set>
  16. #include <cstring>
  17. #include <cassert>
  18. #include <list>
  19. #include <map>
  20. #include <unordered_map>
  21. #include <iomanip>
  22. #include <algorithm>
  23. #include <functional>
  24. #include <utility>
  25. #include <bitset>
  26. #include <cmath>
  27. #include <cstdlib>
  28. #include <ctime>
  29. #include <cstdio>
  30. #include <limits>
  31. using namespace std;
  32. typedef long long          ll;
  33. typedef unsigned long long ull;
  34. typedef long double        ld;
  35. typedef pair<int,int>      pii;
  36. typedef pair<ll,ll>        pll;
  37. typedef vector<int>        vi;
  38. typedef vector<long long>  vll;
  39. #define left(x) 		   (x << 1)
  40. #define right(x) 		   (x << 1) + 1
  41. #define mid(l, r) 	       ((l + r) >> 1)
  42. #define mp                 make_pair
  43. #define pb                 push_back
  44. #define all(a)             a.begin(),a.end()
  45. #define debug(x)	       {cerr <<#x<<" = " <<x<<"\n"; }
  46. #define debug2(x, y)       {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<"\n";}
  47. #define debug3(x, y, z)    {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  48. #define debug4(x, y, z, w) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<", "<<#w << " = " <<w <<"\n";}
  49. #define ss                 second
  50. #define ff                 first
  51. #define m0(x) 		       memset(x,0,sizeof(x))
  52.  
  53. const int mod=1e9+7;
  54.  
  55. template<class T> inline T gcd(T a,T b){ll t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
  56. template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  57. template<typename T, typename S> T expo(T b, S e, const T &m){if(e <= 1)return e == 0?1: b;\
  58. 	return (e&1) == 0?expo((b*b)%m, e>>1, m): (b*expo((b*b)%m, e>>1, m))%m;}
  59. template<typename T> T modinv(T a) { return expo(a, mod-2, mod); }
  60.  
  61. inline int nextint(){ int x; scanf("%d",&x); return x; }
  62. inline ll nextll(){ ll x; scanf("%lld",&x); return x; }
  63.  
  64. const ll  mx_ll   = numeric_limits<ll> :: max();
  65. const int mx_int  = numeric_limits<int> :: max();
  66.  
  67. const long double PI = (long double)(3.1415926535897932384626433832795);
  68.  
  69. #define gc getchar
  70. template <typename T> void scanint(T &x) {
  71. 	T c = gc(); while(((c < 48) || (c > 57)) && (c!='-')) c = gc();
  72. 	bool neg = false; if(c == '-') neg = true; x = 0; for(;c < 48 || c > 57;c=gc());
  73. 	for(;c > 47 && c < 58;c=gc())	x = (x*10) + (c - 48); if(neg)	x = -x;
  74. }
  75.  
  76. const int maxn = 41;
  77. int n , k; 
  78. ll inp[maxn];
  79.  
  80. ll xorit(ll x, ll y) 
  81. {
  82. 	ll ans = 0, mul = 1;
  83. 	for (int i = 0; i < 10; ++i)
  84. 	{
  85. 		int t = x/10;
  86. 		t *= 10;
  87. 		int dig1 = x - t;
  88.  
  89. 		t = y/10;
  90. 		t *= 10;
  91. 		int dig2 = y - t;
  92.  
  93. 		int dig = dig1 + dig2;
  94. 		if(dig >= 10)
  95. 			dig -= 10;
  96. 		ans = ans + 1ll * dig * mul;
  97. 		mul = mul * 10;
  98. 		x /= 10;
  99. 		y /= 10;
  100. 	}
  101. 	return ans;
  102. }
  103.  
  104. int trie[21][1<<19][10];
  105. int sz[21];
  106.  
  107. string convert(ll a)
  108. {
  109. 	string ret;
  110. 	for (int i = 0; i < 10; ++i) 
  111. 	{
  112. 		int t = a/10;
  113. 		t *= 10;
  114. 		int dig = a - t;
  115. 		a /= 10;
  116. 		ret += dig + '0';
  117. 	}
  118. 	return ret;
  119. }
  120.  
  121. inline void insert(ll num,int id)
  122. {
  123. 	int node = 0;
  124. 	string a = convert(num);
  125. 	for(int i = 0; i < 10; i++)
  126. 	{
  127. 		int b = a[9-i]-'0';
  128. 		if(trie[id][node][b] == -1)
  129. 		{
  130. 			trie[id][node][b] = sz[id]++;
  131. 		}
  132. 		node = trie[id][node][b];
  133. 	}
  134. }
  135. inline ll query(ll num,int id)
  136. {
  137.  
  138. 	string a = convert(num);
  139. 	int node = 0;
  140. 	ll ans = 0ll;
  141. 	for(int i = 0; i < 10; i++)
  142. 	{
  143. 		int b = a[9-i]-'0';
  144. 		int found = 0;
  145. 		for(int j = 9-b; j >= 0; j--)
  146. 		{
  147. 			if(trie[id][node][j] != -1)
  148. 			{
  149. 				found = 1;
  150. 				ans = ans * 10 + (j+b);
  151. 				node = trie[id][node][j];
  152. 				break;
  153. 			}
  154. 		}
  155. 		if(found)
  156. 			continue;
  157. 		else
  158. 		{
  159. 			for(int j = 9; j > 9-b; j--)  
  160. 			{
  161. 				if(trie[id][node][j] != -1)
  162. 				{
  163. 					found = 1;
  164. 					ans = ans * 10 + (j+b-10);
  165. 					node = trie[id][node][j];
  166. 					break;
  167. 				}
  168. 			}
  169. 		}
  170.  
  171. 	}
  172. 	return ans;
  173. }
  174. int main()
  175. {
  176. 	scanf("%d%d",&n,&k);
  177. 	for(int i = 0; i < 21; i++)
  178. 		sz[i] = 1;
  179. 	for(int i = 0; i < 21; i++)
  180. 	{
  181. 		for(int j = 0; j < (1<<19); j++)
  182. 		{
  183. 			for(int k = 0; k < 10; k++)
  184. 			{
  185. 				trie[i][j][k] = -1;  
  186. 			}
  187. 		}
  188. 	}
  189. 	for(int i = 0; i < n; i++)
  190. 		scanf("%lld",&inp[i]);
  191.  
  192. 	if(k == 1)
  193. 	{
  194. 		cout << *max_element(inp,inp+n) << "\n";  
  195. 		return 0;
  196. 	}
  197. 	int nhalf = n/2;
  198. 	int pow2[21];
  199. 	for(int i = 0; i < 21; i++)
  200. 		pow2[i] = 1<<i;
  201.  
  202. 	int lim = (1<<nhalf);
  203. 	for(int mask = 0; mask < lim; mask++)
  204. 	{
  205. 		int szmask = __builtin_popcount(mask);
  206. 		if( szmask > k ) continue;
  207. 		ll num = 0;
  208. 		int size_subset = 0;
  209. 		for(int i = 0; i < nhalf; i++)
  210. 			if(mask & pow2[i])
  211. 			{
  212. 				num = xorit(num,inp[i]);  
  213. 				size_subset++;
  214. 			}
  215. 		insert(num,size_subset);
  216. 	}
  217. 	ll ans = -1;
  218. 	lim = (1<<(n-nhalf));
  219. 	for(int mask = 0; mask < lim; mask++)
  220. 	{
  221. 		int szmask = __builtin_popcount(mask);
  222. 		if( (szmask > k) || sz[k-szmask] == 1 ) continue;
  223.  
  224. 		int size_subset = 0;
  225. 		ll num = 0ll;
  226. 		for(int i = 0; i < (n-nhalf); i++)
  227. 			if(mask & pow2[i])
  228. 			{
  229. 				num = xorit(num,inp[i+nhalf]);  
  230. 				size_subset++;
  231. 			}
  232. 		if(k >= size_subset && k - size_subset <= nhalf)
  233. 		{
  234. 			ans = max( ans , query(num,k-size_subset));
  235. 		}
  236. 	}
  237. 	printf("%lld\n",ans);
  238. 	return 0;
  239. }
  240.  
  241.  
  242.  
  243.  
Success #stdin #stdout 0.12s 433536KB
comments (?)
stdin
copy 
3 2
4 1 5
stdout
copy 
9
https://ideone.com/CgqR3z
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!