fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef double db; 
  7. typedef string str; 
  8.  
  9. typedef pair<int,int> pi;
  10. typedef pair<ll,ll> pl; 
  11. typedef pair<db,db> pd; 
  12.  
  13. typedef vector<int> vi; 
  14. typedef vector<ll> vl; 
  15. typedef vector<db> vd; 
  16. typedef vector<str> vs; 
  17. typedef vector<pi> vpi;
  18. typedef vector<pl> vpl; 
  19. typedef vector<pd> vpd; 
  20.  
  21. #define mp make_pair
  22. #define f first
  23. #define s second
  24. #define sz(x) (int)x.size()
  25. #define all(x) begin(x), end(x)
  26. #define rall(x) (x).rbegin(), (x).rend() 
  27. #define rsz resize
  28. #define ins insert 
  29. #define ft front() 
  30. #define bk back()
  31. #define pf push_front 
  32. #define pb push_back
  33. #define eb emplace_back 
  34. #define lb lower_bound 
  35. #define ub upper_bound 
  36.  
  37. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  38. #define F0R(i,a) FOR(i,0,a)
  39. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  40. #define R0F(i,a) ROF(i,0,a)
  41. #define trav(a,x) for (auto& a: x)
  42.  
  43. const int MOD = 1e9+7; // 998244353;
  44. const int MX = 2e5+5; 
  45. const ll INF = 1e18; 
  46. const ld PI = acos((ld)-1);
  47. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
  48. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
  49.  
  50. template<class T> bool ckmin(T& a, const T& b) { 
  51. 	return b < a ? a = b, 1 : 0; }
  52. template<class T> bool ckmax(T& a, const T& b) { 
  53. 	return a < b ? a = b, 1 : 0; } 
  54. int pct(int x) { return __builtin_popcount(x); } 
  55. int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
  56. int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
  57. int fstTrue(function<bool(int)> f, int lo, int hi) {
  58. 	hi ++; assert(lo <= hi); // assuming f is increasing
  59. 	while (lo < hi) { // find first index such that f is true 
  60. 		int mid = (lo+hi)/2; 
  61. 		f(mid) ? hi = mid : lo = mid+1; 
  62. 	} 
  63. 	return lo;
  64. }
  65.  
  66. // INPUT
  67. template<class A> void re(complex<A>& c);
  68. template<class A, class B> void re(pair<A,B>& p);
  69. template<class A> void re(vector<A>& v);
  70. template<class A, size_t SZ> void re(array<A,SZ>& a);
  71.  
  72. template<class T> void re(T& x) { cin >> x; }
  73. void re(db& d) { str t; re(t); d = stod(t); }
  74. void re(ld& d) { str t; re(t); d = stold(t); }
  75. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  76.  
  77. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  78. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  79. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  80. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  81.  
  82. // TO_STRING
  83. #define ts to_string
  84. str ts(char c) { return str(1,c); }
  85. str ts(bool b) { return b ? "true" : "false"; }
  86. str ts(const char* s) { return (str)s; }
  87. str ts(str s) { return s; }
  88. template<class A> str ts(complex<A> c) { 
  89. 	stringstream ss; ss << c; return ss.str(); }
  90. str ts(vector<bool> v) { 
  91. 	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  92. 	res += "}"; return res; }
  93. template<size_t SZ> str ts(bitset<SZ> b) {
  94. 	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  95. 	return res; }
  96. template<class A, class B> str ts(pair<A,B> p);
  97. template<class T> str ts(T v) { // containers with begin(), end()
  98. 	bool fst = 1; str res = "{";
  99. 	for (const auto& x: v) {
  100. 		if (!fst) res += ", ";
  101. 		fst = 0; res += ts(x);
  102. 	}
  103. 	res += "}"; return res;
  104. }
  105. template<class A, class B> str ts(pair<A,B> p) {
  106. 	return "("+ts(p.f)+", "+ts(p.s)+")"; }
  107.  
  108. // OUTPUT
  109. template<class A> void pr(A x) { cout << ts(x); }
  110. template<class H, class... T> void pr(const H& h, const T&... t) { 
  111. 	pr(h); pr(t...); }
  112. void ps() { pr("\n"); } // print w/ spaces
  113. template<class H, class... T> void ps(const H& h, const T&... t) { 
  114. 	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  115.  
  116. // DEBUG
  117. void DBG() { cerr << "]" << endl; }
  118. template<class H, class... T> void DBG(H h, T... t) {
  119. 	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  120. 	DBG(t...); }
  121. #ifdef LOCAL // compile with -DLOCAL
  122. #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  123. #else
  124. #define dbg(...) 0
  125. #endif
  126.  
  127. // FILE I/O
  128. void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  129. void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  130. void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
  131. void setIO(string s = "") {
  132. 	unsyncIO();
  133. 	// cin.exceptions(cin.failbit); 
  134. 	// throws exception when do smth illegal
  135. 	// ex. try to read letter into int
  136. 	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  137. }
  138.  
  139. // INITIALIZE ARRAYS TO ZERO
  140.  
  141. struct EllysNim {
  142. 	void gen(int seed) {
  143. 		ll state = seed;
  144. 		while (1) {
  145. 			state = (state * 1103515245 + 12345) % (1LL<<31);
  146.  
  147. 		}
  148. 	}
  149. 	ll rec(vi A, int b, bool done = 0) { // done: whether x=2 was chosen yet
  150. 		ll sum = 0;
  151. 		trav(t,A) if ((t>>(b+1))&1) {
  152. 			sum += 1<<(b+1);
  153. 			t -= 1<<(b+1);
  154. 		}
  155. 		if (b == -1) return sum;
  156. 		sort(all(A));
  157. 		int cnt = 0; trav(t,A) cnt ^= (t>>b)&1;
  158. 		int ind = -1; while (ind+1 < sz(A) && !(A[ind+1]&(1<<b))) ind ++;
  159. 		if (cnt == 1) { // try x=1
  160. 			if (ind == -1) return INF;
  161. 			A[ind] = 1<<b; return rec(A,b-1,done)+sum;
  162. 		} else {
  163. 			ll bes = rec(A,b-1,done); // try x=0
  164. 			if (!done && ind >= 1) { // try x=2
  165. 				A[ind-1] = A[ind] = 1<<b;
  166. 				ckmin(bes,rec(A,b-1,1));
  167. 			}
  168. 			return bes+sum;
  169. 		}
  170. 	}
  171. 	long long getMin(vector <int> A) {
  172. 		ll res = rec(A,30); trav(t,A) res -= t;
  173. 		return res;
  174. 	}
  175. };
  176.  
  177. int main() {
  178. 	EllysNim c; ps(c.getMin({42, 13, 123, 55, 666, 17}));
  179. 	ps(c.getMin({1,1}));
  180. }
  181.  
  182. /* stuff you should look for
  183. 	* int overflow, array bounds
  184. 	* special cases (n=1?)
  185. 	* do smth instead of nothing and stay organized
  186. 	* WRITE STUFF DOWN
  187. */
  188.  
  189.  
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
480
0
https://ideone.com/i9uiHF
EllysNim (Public)
language:
C++14 (gcc 8.3)
created:
3 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!