Guest User

Untitled

a guest
Jun 30th, 2020
33
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4. #include <cmath>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. using namespace __gnu_pbds;
  8. using namespace std;
  9.  
  10. #define rep(i, n) for(ll i = 0; i < (ll)n; i++)
  11. #define repi(i, a, n) for(ll i = a; i < (ll)n; i++)
  12. #define repii(i, a, n, b) for(ll i = a; i < (ll)n; i+=b)
  13. #define pb push_back
  14. #define vi vector <int>
  15. #define vll vector <ll>
  16. #define vpll vector <pair <ll, ll> >
  17. #define all(v) v.begin(), v.end()
  18. #define M_PI 3.14159265358979323846
  19. #define bs binary_search
  20. #define ff first
  21. #define ss second
  22. #define ordered_set tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
  23.  
  24.  
  25. typedef long long ll;
  26. const long long max_sz = 1e2 + 1;
  27. const long long mod = 1e9 + 7;
  28. const long long MAXN = 4e18 + 1;
  29.  
  30. // DEBUGGING TEMPLATE
  31. void __print(int x) {cerr << x;}
  32. void __print(long x) {cerr << x;}
  33. void __print(long long x) {cerr << x;}
  34. void __print(unsigned x) {cerr << x;}
  35. void __print(unsigned long x) {cerr << x;}
  36. void __print(unsigned long long x) {cerr << x;}
  37. void __print(float x) {cerr << x;}
  38. void __print(double x) {cerr << x;}
  39. void __print(long double x) {cerr << x;}
  40. void __print(char x) {cerr << '\'' << x << '\'';}
  41. void __print(const char *x) {cerr << '\"' << x << '\"';}
  42. void __print(const string &x) {cerr << '\"' << x << '\"';}
  43. void __print(bool x) {cerr << (x ? "true" : "false");}
  44. template<typename T, typename V>
  45. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  46. template<typename T>
  47. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  48. void _print() {cerr << "]\n";}
  49. template <typename T, typename... V>
  50. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  51. #ifndef ONLINE_JUDGE
  52. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  53. #else
  54. #define debug(x...)
  55. #endif
  56.  
  57. ll gcd(ll a, ll b){
  58. if(b == 0) return a;
  59. return gcd(b, a%b);
  60. }
  61.  
  62. void print(vll v){
  63. rep(i, v.size()) cout << v[i] << " ";
  64. cout << endl;
  65. }
  66.  
  67. vll div(ll n){
  68. vll v;
  69. repi(i, 1, sqrt(n)+1){
  70. if((n%i) == 0){
  71. if(i == n/i) v.pb(i);
  72. else v.pb(i), v.pb(n/i);}
  73. }
  74. return v;
  75. }
  76.  
  77. ll powmod(ll a, ll b, ll c){
  78. if(b == 0) return 1%c;
  79. else if(b % 2 == 0) return powmod((a*a)%c, b/2, c);
  80. return (a*powmod((a*a)%c, (b-1)/2, c))%c;
  81. }
  82.  
  83. void printp(vpll v){
  84. rep(i, v.size()) cout << v[i].first << " " << v[i].second << endl;
  85. }
  86.  
  87. ll min(ll a, ll b){
  88. return a < b ? a : b;
  89. }
  90.  
  91. ll max(ll a, ll b){
  92. return a > b ? a : b;
  93. }
  94.  
  95. ll min3(ll a, ll b, ll c){
  96. return min(min(a, b), c);
  97. }
  98.  
  99. void print_map(map <ll, ll> m){
  100. for(auto it : m) cout << it.first << " " << it.second << "\n";
  101. }
  102.  
  103.  
  104. void print_set(set <ll> s){
  105. for(auto it : s) cout << it << " ";
  106. cout << endl;
  107. }
  108.  
  109. ll inv(ll a){
  110. return powmod(a, mod-2, mod);
  111. }
  112.  
  113.  
  114. bool prime[max_sz];
  115. // Sieve of erathosthenes
  116. void sieve(){
  117. memset(prime, true, sizeof(prime));
  118. for(ll i = 2; i * i < max_sz; i++){
  119. if(prime[i] == true){
  120. for(ll j = i*i ; j < max_sz; j+=i){
  121. prime[j] = false;
  122. }
  123. }
  124. }
  125. }
  126.  
  127. vll pow(ll a){
  128. vll res;
  129. ll temp = 1;
  130. while(temp <= MAXN){
  131. res.pb(temp);
  132. temp *= a;
  133. }
  134. return res;
  135. }
  136.  
  137.  
  138. vll v(max_sz), powers(max_sz), inverse(max_sz);
  139. void fact(){
  140. v[0] = 1;
  141. repi(i, 1, max_sz) v[i] = (v[i-1]*i)%mod;
  142. rep(i, max_sz) inverse[i] = powmod(v[i], mod - 2, mod);
  143. }
  144.  
  145.  
  146. // Obtain the binomial coefficients modulo mod
  147. ll binom(ll n, ll p){
  148. if(n < p || p < 0) return 0;
  149. // ll tmp1 = powmod(v[p], mod-2, mod);
  150. // ll tmp2 = powmod(v[n - p], mod-2, mod);
  151. ll d = ((inverse[p] * inverse[n - p])%mod * v[n]) % mod;
  152. return d;
  153. }
  154.  
  155.  
  156.  
  157. //Obtain the smallest x such that ax = 1 mod m and (a, m) = 1
  158. ll modinv(ll a, ll m){
  159. ll m0 = m, y = 0, x = 1;
  160. if (m == 1) return 0;
  161. while (a > 1){
  162. ll q = a / m, t = m;
  163. m = a % m, a = t;
  164. t = y, y = x - q * y, x = t;
  165. }
  166. if (x < 0) x += m0;
  167. return x;
  168. }
  169.  
  170. void swap(ll &a, ll &b){
  171. {
  172. ll temp = a;
  173. a = b;
  174. b = temp;
  175. }
  176. }
  177.  
  178. ll spf[max_sz];
  179. //Compute the smallest prime factor of all numbers
  180. void smallest_prime(){
  181. spf[1] = 1;
  182. for(ll i = 2; i <= max_sz; i++) spf[i] = i;
  183. for (ll i = 4; i <= max_sz; i += 2) spf[i] = 2;
  184. for (ll i = 3; i * i <= max_sz; i++){
  185. if (spf[i] == i){
  186. for (ll j= i * i; j <= max_sz; j+=i)
  187. if (spf[j] == j) spf[j] = i;
  188. }
  189. }
  190. }
  191.  
  192.  
  193. //Prime factorise a number in O(log n) time
  194. vll factorise(ll x){
  195. vector<ll> res;
  196. while (x != 1){
  197. res.push_back(spf[x]);
  198. x = x / spf[x];
  199. }
  200. return res;
  201. }
  202.  
  203. //Obtain the digits in the decimal 10 representation of number n
  204. vll digits(ll n){
  205. vll res;
  206. while(n != 0){
  207. res.pb(n % 10);
  208. n /= 10;
  209. }
  210. // sort(all(res));
  211. return res;
  212. }
  213.  
  214. //Check if a is a suffix of b
  215. ll suffix(string a, string b){
  216. if(a.size() > b.size()) return 0;
  217. for(ll i = a.size() - 1; i >= 0; --i){
  218. if(b[b.size() - 1 - (a.size() - 1 - i)]) return 0;
  219. }
  220. return 1;
  221. }
  222.  
  223.  
  224. ll inc(vll a){
  225. rep(i, a.size() - 1) if(a[i + 1] < a[i]) return 0;
  226. return 1;
  227. }
  228.  
  229. ll dec(vll a){
  230. rep(i, a.size() - 1) if(a[i + 1] > a[i]) return 0;
  231. return 1;
  232. }
  233.  
  234. vll bin(ll a){
  235. vll res;
  236. while(a != 0) res.pb(a % 2), a /= 2;
  237. while((ll)res.size() != 36) res.pb(0);
  238. return res;
  239. }
  240.  
  241. ll up(ll a, ll b){
  242. if(a % b == 0) return a / b;
  243. return a / b + 1;
  244. }
  245.  
  246. // #define ps __builtin_popcount
  247.  
  248. vll dig(ll n){
  249. vll res;
  250. if(n == 0) {res.pb(0); return res;}
  251. while(n != 0) res.pb(n % 10), n /= 10;
  252. return res;
  253. }
  254.  
  255.  
  256. // Sort a pair in decreasing order by first element
  257. bool inrev(const pair <ll, ll> &a, const pair <ll, ll> &b){
  258. return a.ff > b.ff;
  259. if(a.ff == b.ff) return a.ss < b.ss;
  260. }
  261.  
  262. #define ff first
  263. #define ss second
  264.  
  265. #define IOS ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
  266.  
  267. const ll nax = 2e5 + 5;
  268. vll pos[nax];
  269.  
  270. // vll two = pow(2);
  271. vll ten = pow(10);
  272.  
  273.  
  274. pair <ll, ll> naive(vll a, ll k, ll x){
  275. rep(i, k){
  276. sort(all(a));
  277. debug(a);
  278. rep(j, a.size()) if(j % 2 == 0) a[j] = a[j] ^ x;
  279. }
  280. sort(all(a));
  281. ll mx = a[a.size() - 1], mn = a[0];
  282. pair <ll, ll> p = {mx, mn};
  283. return p;
  284. }
  285.  
  286. int main(){
  287. ll t = 1;
  288. // cin >> t;
  289. while(t--){
  290. ll n, k, x;
  291. cin >> n >> k >> x;
  292. vll a(n);
  293. rep(i, n) cin >> a[i];
  294. vll b = a;
  295. map <vector <ll>, ll> m;
  296. ll pos = -1, cycle = -1;
  297. sort(all(a));
  298. m.insert({a, 0});
  299. repi(i, 1, k + 1){
  300. debug(a);
  301. rep(j, n) if(j % 2 == 0){
  302. a[j] = a[j] ^ x;
  303. }
  304. sort(all(a));
  305. auto it = m.find(a);
  306. if(it != m.end()) {cycle = i - it -> ss, pos = i; break;}
  307. m.insert({a, i});
  308. }
  309. debug(pos, cycle);
  310. if(pos == -1 || (k - pos) % cycle == 0){
  311. sort(all(a));
  312. ll mx = a[n - 1], mn = a[0];
  313. debug(mx, mn);
  314. cout << mx << " " << mn << endl;
  315. }
  316. else{
  317. ll rem = (k - pos) % cycle;
  318. ll till = pos - cycle + rem;
  319. for(auto it : m) if(it.ss == till){
  320. vll res = it.ff;
  321. sort(all(res));
  322. ll mx = res[n - 1], mn = res[0];
  323. cout << mx << " " << mn << endl;
  324. }
  325.  
  326. }
  327. // pair <ll, ll> res = naive(b, k, x);
  328. // debug(res.ff, res.ss);
  329. }
  330. }
RAW Paste Data