codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1361.md (14222B)


      1 Source: https://codeforces.com/blog/entry/78355
      2 
      3 [1362A - Johnny and Ancient Computer](/contest/1362/problem/A "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!")
      4 
      5 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 typedef long long LL;
     19 
     20 LL getR(LL a){
     21 	while(a % 2 == 0)
     22 		a /= 2;
     23 	return a;
     24 }
     25 
     26 void solve(){
     27 	LL a, b;
     28 	scanf("%lld %lld", &a, &b);
     29 	if(a > b)	swap(a, b);
     30 	
     31 	LL r = getR(a);
     32 	if(getR(b) != r){
     33 		puts("-1");
     34 		return;
     35 	}
     36 	
     37 	int ans = 0;
     38 	b /= a;
     39 	
     40 	while(b >= 8)
     41 		b /= 8, ++ans;
     42 	if(b > 1)	++ans;
     43 	printf("%d\n", ans);
     44 }
     45 
     46 int main(){
     47 	int quest;
     48 	scanf("%d", &quest);
     49 	
     50 	while(quest--)
     51 		solve();
     52 	return 0;
     53 }
     54 ```
     55 
     56 [1362B - Johnny and His Hobbies](/contest/1362/problem/B "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!")
     57 
     58 Authors: [Anadi](/profile/Anadi "International Grandmaster Anadi") and [Okrut](/profile/Okrut "Master Okrut")
     59 
     60 **Tutorial**
     61 
     62 Tutorial is loading...
     63 
     64 **Solution**
     65 
     66 ```
     67 //O(n * maxA) solution
     68 
     69 #include <bits/stdc++.h>
     70 
     71 using namespace std;
     72 
     73 const int N = 1025;
     74 
     75 int n;
     76 int in[N];
     77 bool is[N];
     78 
     79 bool check(int k){
     80 	for(int i = 1; i <= n; ++i)
     81 		if(!is[in[i] ^ k])
     82 			return false;
     83 	return true;
     84 }
     85 
     86 void solve(){
     87 	for(int i = 0; i < N; ++i)
     88 		is[i] = false;
     89 	
     90 	scanf("%d", &n);
     91 	for(int i = 1; i <= n; ++i){
     92 		scanf("%d", &in[i]);
     93 		is[in[i]] = true;
     94 	}
     95 	
     96 	for(int k = 1; k < 1024; ++k)
     97 		if(check(k)){
     98 			printf("%d\n", k);
     99 			return;
    100 		}
    101 	
    102 	puts("-1");
    103 }
    104 
    105 int main(){
    106 	int cases;
    107 	scanf("%d", &cases);
    108 	
    109 	while(cases--)
    110 		solve();
    111 	return 0;
    112 }
    113 ```
    114 
    115 [1362C - Johnny and Another Rating Drop](/contest/1362/problem/C "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!")
    116 
    117 Author: [MicGor](/profile/MicGor "International Grandmaster MicGor")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution**
    124 
    125 ```
    126 #include <bits/stdc++.h>
    127 
    128 using namespace std;
    129 
    130 typedef long long LL;
    131 
    132 void solve(){
    133 	LL a;
    134 	scanf("%lld", &a);
    135 	
    136 	LL ans = 0;
    137 	for(int i = 0; i < 60; ++i)
    138 		if(a & (1LL << i))
    139 			ans += (1LL << (i + 1)) - 1;
    140 	printf("%lld\n", ans);
    141 }
    142 
    143 int main(){
    144 	int quest;
    145 	scanf("%d", &quest);
    146 	
    147 	while(quest--)
    148 		solve();
    149 	return 0;
    150 }
    151 ```
    152 
    153 [1361A - Johnny and Contribution](/contest/1361/problem/A "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    154 
    155 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi")
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 
    166 using namespace std;
    167 
    168 const int N = 1e6 + 7;
    169 
    170 int n, m;
    171 int ans[N];
    172 
    173 int last[N];
    174 vector <int> G[N];
    175 vector <int> in[N];
    176 
    177 int main(){
    178 	scanf("%d %d", &n, &m);
    179 	for(int i = 1; i <= m; ++i){
    180 		int u, v;
    181 		scanf("%d %d", &u, &v);
    182 		
    183 		G[u].push_back(v);
    184 		G[v].push_back(u);
    185 	}
    186 	
    187 	for(int i = 1; i <= n; ++i){
    188 		int color;
    189 		scanf("%d", &color);
    190 
    191 		in[color].push_back(i);
    192 		if(color > n){
    193 			puts("-1");
    194 			exit(0);
    195 		}
    196 	}
    197 	
    198 	vector <int> result;
    199 	for(int i = 1; i <= n; ++i){
    200 		for(auto u: in[i]){
    201 			for(auto v: G[u])
    202 				last[ans[v]] = u;
    203 			
    204 			ans[u] = 1;
    205 			while(last[ans[u]] == u)
    206 				++ans[u];
    207 			
    208 			if(ans[u] != i){
    209 				puts("-1");
    210 				exit(0);
    211 			}
    212 			
    213 			result.push_back(u);
    214 		}
    215 	}
    216 	
    217 	for(int i = 0; i < n; ++i)
    218 		printf("%d%c", result[i], i == n - 1 ? '\n' : ' ');
    219 	return 0;
    220 }
    221 ```
    222 
    223 [1361B - Johnny and Grandmaster](/contest/1361/problem/B "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    224 
    225 Author: [Okrut](/profile/Okrut "Master Okrut")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235 using namespace std;
    236 typedef long long ll;
    237 
    238 const ll INF = 1e6+100;
    239 const ll mod = ll(1e9)+7;
    240 
    241 ll fexp (ll a, int e)
    242 {
    243 	ll ret = 1LL;
    244 	while (e>0)
    245 	{
    246 		if (e%2==1) ret = ret * a % mod;
    247 		a = a*a % mod;
    248 		e/=2;
    249 	}
    250 	return ret;
    251 }
    252 
    253 int main ()
    254 {
    255 	int t;
    256 	scanf ("%d", &t);
    257 	for (int test = 0; test < t; test++)
    258 	{
    259 		int n;
    260 		ll p;
    261 		scanf ("%d %lld", &n, &p);
    262 		vector <int> K(n);
    263 		for (int &x: K) scanf ("%d", &x);
    264 		sort(K.begin(), K.end());
    265 		
    266 		vector <int> Exp = K;
    267 		
    268 		ll currSum = 0;
    269 		ll result = 0;
    270 		bool infty = false;
    271 		
    272 		int prevExp = 1e6+10;
    273 		while (!Exp.empty())
    274 		{
    275 			/* Update the currSum and result (multiply by a power of k) */
    276 			int k = Exp.back();
    277 			Exp.pop_back();
    278 			int delta = prevExp - k;
    279 			prevExp = k;
    280 			
    281 			result = result * fexp(p, delta) % mod;
    282 			
    283 			/* Multiplying by p 20 times will either 
    284 			not change the currSum at all or make it bigger than n */
    285 			for (int i=0; i<min(delta, 20); i++)
    286 			{
    287 				currSum *= p;
    288 				if (currSum > INF) infty = true;
    289 			}
    290 			
    291 			/* Process all the elements equal p^k */
    292 			while (!K.empty() && K.back()==k)
    293 			{
    294 				K.pop_back();
    295 				if (infty || currSum > 0)
    296 				{
    297 					currSum--;
    298 					result+=mod - 1;
    299 				}
    300 				else
    301 				{
    302 					currSum++;
    303 					result++;
    304 				}
    305 				result%=mod;
    306 			}
    307 		}
    308 		
    309 		result = result * fexp(p, prevExp) % mod;
    310 		
    311 		printf ("%lld\n", result % mod);
    312 	}
    313 }
    314 ```
    315 
    316 [1361C - Johnny and Megan's Necklace](/contest/1361/problem/C "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    317 
    318 Author: [Okrut](/profile/Okrut "Master Okrut")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328 
    329 using namespace std;
    330 
    331 #define st first
    332 #define nd second
    333 #define PII pair <int, int>
    334 
    335 const int N = 1 << 20;
    336 
    337 int n;
    338 int part[N][2];
    339 
    340 bool vis[N];
    341 vector <int> ans;
    342 vector <PII> G[N];
    343 
    344 //mark whole component as visited
    345 void dfs(int u){
    346 	vis[u] = true;
    347 	for(auto v: G[u])
    348 		if(!vis[v.st])
    349 			dfs(v.st);
    350 }
    351 
    352 //check if the graph for a given Mask is correct
    353 bool check(int Mask){
    354 	for(int i = 0; i <= Mask; ++i)
    355 		G[i].clear(), vis[i] = false;
    356 
    357 	for(int i = 1; i <= n; ++i){
    358 		int u = part[i][0] & Mask;
    359 		int v = part[i][1] & Mask;
    360 		
    361 		G[u].push_back({v, 2 * i - 1});
    362 		G[v].push_back({u, 2 * i - 2});
    363 	}
    364 	
    365 	//calculate number of components and check if all degrees are even
    366 	int comps = 0;
    367 	for(int i = 0; i <= Mask; ++i){
    368 		if(G[i].size() & 1)
    369 			return false;
    370 		
    371 		if(!vis[i] && G[i].size() > 0){
    372 			++comps;
    373 			dfs(i);
    374 		}
    375 	}
    376 	
    377 	return comps == 1;
    378 }
    379 
    380 //find euler cycle
    381 void go(int u, int prv = -1){
    382 	while(G[u].size()){
    383 		auto e = G[u].back();
    384 		G[u].pop_back();
    385 
    386 		if(vis[e.nd / 2])
    387 			continue;
    388 		
    389 		vis[e.nd / 2] = true;
    390 		go(e.st, e.nd);
    391 	}
    392 	
    393 	if(prv != -1){
    394 		ans.push_back(prv);
    395 		ans.push_back(prv ^ 1);
    396 	}
    397 }
    398 
    399 //restore the sequence corresponding to the result for given mask
    400 //the result is already checked so the graph is built
    401 void restore(int Mask){
    402 	for(int i = 0; i <= n; ++i)
    403 		vis[i] = false;
    404 	
    405 	for(int i = 0; i <= Mask; ++i)
    406 		if(G[i].size()){
    407 			go(i);
    408 			break;
    409 		}
    410 	
    411 	//cycle is reversed but thats fine
    412 	for(int i = 0; i < n + n; ++i)
    413 		printf("%d%c", ans[i] + 1, " \n"[i + 1 == n + n]);
    414 }
    415 
    416 int main(){
    417 	scanf("%d", &n);
    418 	for(int i = 1; i <= n; ++i)
    419 		scanf("%d %d", &part[i][0], &part[i][1]);
    420 
    421 	for(int i = 20; i >= 0; --i)
    422 		if(check((1 << i) - 1)){
    423 			printf("%d\n", i);
    424 			restore((1 << i) - 1);
    425 			exit(0);
    426 		}
    427 	
    428 	assert(false);
    429 	return 0;
    430 }
    431 ```
    432 
    433 [1361D - Johnny and James](/contest/1361/problem/D "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    434 
    435 Author: [Okrut](/profile/Okrut "Master Okrut")
    436 
    437 **Tutorial**
    438 
    439 Tutorial is loading...
    440 
    441 **Solution**
    442 
    443 ```
    444 #include <bits/stdc++.h>
    445 
    446 using namespace std;
    447 
    448 typedef long double T;
    449 
    450 #define st first
    451 #define nd second
    452 #define PII pair <int, int>
    453 
    454 const int N = 1e6 + 7;
    455 
    456 int n, m, k;
    457 vector <T> arms[N];
    458 
    459 void read(){
    460 	map <PII, int> M;
    461 
    462 	scanf("%d %d", &n, &k);	
    463 	for(int i = 1; i <= n; ++i){
    464 		int x, y;
    465 		scanf("%d %d", &x, &y);
    466 		
    467 		if(x == 0 && y == 0)
    468 			continue;
    469 		
    470 		int d = __gcd(abs(x), abs(y));
    471 		PII my_id = {x / d, y / d};
    472 		
    473 		if(!M.count(my_id))
    474 			M[my_id] = ++m;
    475 		
    476 		auto id = M[my_id];
    477 		arms[id].push_back(sqrtl((T)x * x + (T)y * y));
    478 	}
    479 	
    480 	for(int i = 1; i <= m; ++i){
    481 		sort(arms[i].begin(), arms[i].end());
    482 		reverse(arms[i].begin(), arms[i].end());
    483 	}
    484 }
    485 
    486 T solve_center(){
    487 	T ans = 0;
    488 	vector <T> vals = {0};
    489 
    490 	for(int i = 1; i <= m; ++i){
    491 		int it = 0;
    492 		for(auto v: arms[i]){
    493 			++it;
    494 			vals.push_back(v * (k - it - it + 1));
    495 		}
    496 	}
    497 	
    498 	sort(vals.begin(), vals.end());
    499 	reverse(vals.begin(), vals.end());
    500 
    501 	for(int i = 0; i < k; ++i)
    502 		ans += vals[i];
    503 	return ans;
    504 }
    505 
    506 T solve_arm(int id){
    507 	T ans = 0;
    508 	for(int i = 1; i <= m; ++i){
    509 		if(i == id)
    510 			continue;
    511 		
    512 		int it = 0;
    513 		for(auto v: arms[i]){
    514 			++it;
    515 			ans += v * (k - it - it + 1);
    516 		}
    517 	}
    518 	
    519 	int half = k / 2;
    520 	int first_half = k - half - (n - arms[id].size());
    521 		
    522 	for(int i = 0; i < half; ++i)
    523 		ans += arms[id][i] * (k - i - i - 1);
    524 	
    525 	for(int i = 0; i < first_half; ++i){
    526 		T val = arms[id][arms[id].size() - i - 1];
    527 		ans += val * (k - half - half - 2 * first_half + 2 * i + 1);
    528 	}
    529 	
    530 	return ans;
    531 }
    532 
    533 int main(){
    534 	read();
    535 	T ans = solve_center();
    536 	if(k < n){
    537 		for(int i = 1; i <= m; ++i)
    538 			if(2 * (n - (int)arms[i].size()) <= k)
    539 				ans = max(ans, solve_arm(i));
    540 	}
    541 
    542 	printf("%.10Lf\n", ans);
    543 	return 0;
    544 }
    545 ```
    546 
    547 [1361E - James and the Chase](/contest/1361/problem/E "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    548 
    549 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi")
    550 
    551 **Tutorial**
    552 
    553 Tutorial is loading...
    554 
    555 **Solution**
    556 
    557 ```
    558 #include <bits/stdc++.h>
    559 
    560 using namespace std;
    561 
    562 const int N = 1e5 + 7;
    563 
    564 int n, m;
    565 bool bad[N];
    566 vector <int> G[N];
    567 
    568 int vis[N];
    569 bool interesting;
    570 
    571 int lvl[N];
    572 int best[N];
    573 int balance[N];
    574 
    575 void clear(){
    576 	for(int i = 1; i <= n; ++i){
    577 		lvl[i] = 0;
    578 		best[i] = 0;
    579 		balance[i] = 0;
    580 
    581 		G[i].clear();		
    582 		bad[i] = false;
    583 	}
    584 }
    585 
    586 void no_answer(){
    587 	puts("-1");
    588 	clear();
    589 }
    590 
    591 int getInt(int a = INT_MIN, int b = INT_MAX){
    592 	static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    593 	return uniform_int_distribution <int> (a, b)(rng);
    594 }
    595 
    596 void dfs(int u){
    597 	vis[u] = 1;
    598 	for(auto v: G[u])
    599 		if(vis[v] == 0)
    600 			dfs(v);
    601 		else if(vis[v] == 2)
    602 			interesting = false;
    603 	vis[u] = 2;
    604 }
    605 
    606 bool check(int r){
    607 	for(int i = 1; i <= n; ++i)
    608 		vis[i] = 0;
    609 	interesting = true;
    610 
    611 	dfs(r);
    612 	return interesting;
    613 }
    614 
    615 int find_any(){
    616 	int tests = 100;
    617 	while(tests--){
    618 		int r = getInt(1, n);
    619 		if(check(r))
    620 			return r;
    621 	}
    622 	
    623 	return -1;
    624 }
    625 
    626 int find_bad(int u){
    627 	vis[u] = 1;
    628 	best[u] = u;
    629 	for(auto v: G[u])
    630 		if(vis[v] == 0){
    631 			lvl[v] = lvl[u] + 1;
    632 			balance[u] += find_bad(v);
    633 			
    634 			if(lvl[best[v]] < lvl[best[u]])
    635 				best[u] = best[v];
    636 		}
    637 		else{
    638 			balance[u]++;
    639 			balance[v]--;
    640 			
    641 			if(lvl[v] < lvl[best[u]])
    642 				best[u] = v;
    643 		}
    644 	
    645 	if(balance[u] > 1)
    646 		bad[u] = true;
    647 	return balance[u];
    648 }
    649 
    650 void propagate_bad(int u){
    651 	vis[u] = 1;
    652 	if(!bad[u] && bad[best[u]])
    653 		bad[u] = true;
    654 
    655 	for(auto v: G[u])
    656 		if(vis[v] == 0)
    657 			propagate_bad(v);
    658 }
    659 
    660 vector <int> find_all(int r){
    661 	for(int i = 1; i <= n; ++i)
    662 		vis[i] = 0;
    663 	vector <int> ans;
    664 
    665 	find_bad(r);
    666 	for(int i = 1; i <= n; ++i)
    667 		vis[i] = 0;
    668 
    669 	propagate_bad(r);
    670 	for(int i = 1; i <= n; ++i)
    671 		if(!bad[i])
    672 			ans.push_back(i);
    673 	return ans;
    674 }
    675 
    676 void solve(){
    677 	scanf("%d %d", &n, &m);
    678 	for(int i = 1; i <= m; ++i){
    679 		int u, v;
    680 		scanf("%d %d", &u, &v);		
    681 		G[u].push_back(v);
    682 	}
    683 	
    684 	int id = find_any();
    685 	if(id == -1){
    686 		no_answer();
    687 		return;
    688 	}
    689 	
    690 	auto ans = find_all(id);
    691 	if(5 * ans.size() >= n){
    692 		for(auto v: ans)
    693 			printf("%d ", v);
    694 		puts("");
    695 		clear();
    696 	}
    697 	else
    698 		no_answer();
    699 }
    700 
    701 int main(){
    702 	int cases;
    703 	scanf("%d", &cases);
    704 	
    705 	while(cases--)
    706 		solve();
    707 	return 0;
    708 }
    709 ```
    710 
    711 [1361F - Johnny and New Toy](/contest/1361/problem/F "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!")
    712 
    713 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi")
    714 
    715 **Tutorial**
    716 
    717 Tutorial is loading...
    718 
    719 **Solution**
    720 
    721 ```
    722 #include <bits/stdc++.h>
    723 #include <ext/pb_ds/assoc_container.hpp>
    724 #include <ext/pb_ds/tree_policy.hpp>
    725 
    726 using namespace std;
    727 using namespace __gnu_pbds;
    728 
    729 typedef long long ll;
    730 typedef tree < int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
    731 
    732 const int N = 2e5 + 7;
    733 
    734 //cartesian tree node
    735 //while creating we calculate set of elements and number of inversions
    736 struct node{
    737 	int splitter = -1;
    738 	long long invs = 0;	
    739 	
    740 	ordered_set S;
    741 	node *left = nullptr, *right = nullptr;
    742 	node(){}
    743 };
    744 
    745 int n;
    746 int in[N];
    747 int weight[N];
    748 
    749 long long ans = 0;
    750 node *root = nullptr;
    751 
    752 void read(){
    753 	scanf("%d", &n);
    754 	for(int i = 1; i <= n; ++i)
    755 		scanf("%d", &in[i]);
    756 	
    757 	for(int i = 1; i < n; ++i)
    758 		scanf("%d", &weight[i]);
    759 }
    760 
    761 //add/delete contribution from fiven node to result
    762 void add_result(node *cur, int mt = 1){
    763 	if(cur -> splitter == 0)
    764 		return;
    765 	ans += mt * min(cur -> invs, (ll)cur -> left -> S.size() * (ll)cur -> right -> S.size() - cur -> invs);
    766 }
    767 
    768 //Create cartesian tree
    769 //Because expected depth is O(logn) we can use bruteforce to find the smallest weight
    770 node* get_cartesian(int from, int to){
    771 	node *ret = new node();
    772 	if(from == to){
    773 		ret -> S.insert(in[from]);
    774 		return ret;
    775 	}
    776 	
    777 	int id = from;
    778 	for(int i = from + 1; i < to; ++i)
    779 		if(weight[i] < weight[id])
    780 			id = i;
    781 	
    782 	ret -> splitter = id;
    783 	ret -> left = get_cartesian(from, id);
    784 	ret -> right = get_cartesian(id + 1, to);
    785 	
    786 	//get elements from ordered set
    787 	for(auto v: ret -> right -> S)
    788 		ret -> S.insert(v);
    789 	
    790 	//calculate number of inversions
    791 	for(auto v: ret -> left -> S){
    792 		ret -> S.insert(v);
    793 		ret -> invs += ret -> right -> S.order_of_key(v);
    794 	}
    795 	
    796 	//add contribution to the result
    797 	add_result(ret);
    798 	return ret;
    799 }
    800 
    801 //depending on mt, removes/add element val on position p
    802 void update_cart(int p, int val, int mt){
    803 	node *cur = root;
    804 	while(cur -> splitter != -1){
    805 		add_result(cur, -1);
    806 		if(mt == -1)
    807 			cur -> S.erase(val);
    808 		else
    809 			cur -> S.insert(val);
    810 		
    811 		if(p <= cur -> splitter){
    812 			cur -> invs += mt * (int)(cur -> right -> S.order_of_key(val));
    813 			cur = cur -> left;
    814 		}
    815 		else{
    816 			cur -> invs += mt * (int)(cur -> left -> S.size() - cur -> left -> S.order_of_key(val));
    817 			cur = cur -> right;
    818 		}
    819 	}
    820 	
    821 	if(mt == -1)
    822 		cur -> S.erase(val);
    823 	else
    824 		cur -> S.insert(val);	
    825 
    826 	cur = root;
    827 	while(cur -> splitter != -1){
    828 		add_result(cur, 1);
    829 		if(p <= cur -> splitter)
    830 			cur = cur -> left;
    831 		else
    832 			cur = cur -> right;
    833 	}
    834 }
    835 
    836 int main(){
    837 	read();
    838 	root = get_cartesian(1, n);
    839 	
    840 	int q;
    841 	scanf("%d", &q);
    842 	while(q--){
    843 		int x, y;
    844 		scanf("%d %d", &x, &y);
    845 		
    846 		if(x == y){
    847 			printf("%lld\n", ans);
    848 			continue;
    849 		}
    850 		
    851 		//remove both numbers
    852 		update_cart(x, in[x], -1);
    853 		update_cart(y, in[y], -1);
    854 		swap(in[x], in[y]);
    855 		
    856 		//add both numbers
    857 		update_cart(x, in[x], 1);
    858 		update_cart(y, in[y], 1);
    859 		printf("%lld\n", ans);
    860 	}
    861 	
    862 	return 0;
    863 }
    864 ```