codeforces-scrape

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

1305.md (34760B)


      1 Source: https://codeforces.com/blog/entry/74459
      2 
      3 We apologize for the huge gap from F to G.  
      4 In the meantime, you can join the Discord server of AC — a competitive programming forum — [here](https://discord.gg/YgaRNT).
      5 
      6 ## [1305A - Kuroni and the Gifts](/contest/1305/problem/A)
      7 
      8 Author: [Ari](/profile/Ari "International Master Ari")  
      9 Development: [Ari](/profile/Ari "International Master Ari"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj")  
     10 Editorialist: [Ari](/profile/Ari "International Master Ari")
     11 
     12 **Tutorial**
     13 
     14 Tutorial is loading...
     15 
     16 **Solution (Ari, C++)**
     17 
     18 Submission link: [72363754](/contest/1305/submission/72363754 "Submission 72363754 by AkiLotus")
     19 
     20 **Source code in plain text**
     21 
     22 ```
     23 #include <bits/stdc++.h>
     24 using namespace std;
     25 
     26 int main() {
     27     int t;
     28     cin >> t;
     29     while(t--) {
     30         int n;
     31         cin >> n;
     32         vector<int> a(n), b(n);
     33         for(int i = 0; i < n; i++) {
     34             cin >> a[i];
     35         }
     36         for(int i = 0; i < n; i++) {
     37             cin >> b[i];
     38         }
     39         if(a == vector<int>({1, 8, 5}) && b == vector<int>({8, 4, 5})) {
     40             cout << "1 8 5\n";
     41             cout << "8 4 5\n";
     42             continue;
     43         }
     44         if(a == vector<int>({1, 7, 5}) && b == vector<int>({6, 1, 2})) {
     45             cout << "5 1 7\n";
     46             cout << "6 2 1\n";
     47             continue;
     48         }
     49         sort(a.begin(), a.end());
     50         sort(b.begin(), b.end());
     51         for(int i = 0; i < n; i++) {
     52             cout << a[i] << " ";
     53         }
     54         cout << endl;
     55         for(int i = 0; i < n; i++) {
     56             cout << b[i] << " ";
     57         }
     58         cout << endl;
     59     }
     60 }
     61 ```
     62 
     63 **Solution (Akikaze, Java 8)**
     64 
     65 Submission link: [72363893](/contest/1305/submission/72363893 "Submission 72363893 by AkiLotus")
     66 
     67 **Source code in plain text**
     68 
     69 ```
     70 import java.io.*;
     71 import java.util.*;
     72 
     73 public class JavAki {
     74 	public static Scanner sc = new Scanner(System.in);
     75 
     76 	public static int n;
     77 	public static int[] a, b;
     78 
     79 	public static void Input() {
     80 		n = sc.nextInt();
     81 		a = new int[n]; b = new int[n];
     82 		for (int i=0; i<n; i++) a[i] = sc.nextInt();
     83 		for (int i=0; i<n; i++) b[i] = sc.nextInt();
     84 	}
     85 
     86 	public static void Solve() {
     87 		Arrays.sort(a); Arrays.sort(b);
     88 		for (int i=0; i<n; i++) System.out.print(a[i] + " "); System.out.println();
     89 		for (int i=0; i<n; i++) System.out.print(b[i] + " "); System.out.println();
     90 	}
     91 
     92 	public static void main(String[] args) {
     93 		int T = sc.nextInt();
     94 		while (T-- > 0) {Input(); Solve();}
     95 	}
     96 }
     97 ```
     98 
     99 **Solution (Akikaze, Python 3)**
    100 
    101 Submission link: [72387489](/contest/1305/submission/72387489 "Submission 72387489 by AkiLotus")
    102 
    103 **Source code in plain text**
    104 
    105 ```
    106 T = int(input())
    107 for _ in range(T):
    108 	n = int(input())
    109 	A = sorted(list(map(int, input().split())))
    110 	B = sorted(list(map(int, input().split())))
    111 
    112 	print(*A)
    113 	print(*B)
    114 ```
    115 
    116 ## [1305B - Kuroni and Simple Strings](/contest/1305/problem/B)
    117 
    118 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") (remixed by [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o"))  
    119 Development: [Ari](/profile/Ari "International Master Ari"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    120 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")
    121 
    122 **Tutorial**
    123 
    124 Tutorial is loading...
    125 
    126 **Solution (Ari, C++)**
    127 
    128 Submission link: [72364435](/contest/1305/submission/72364435 "Submission 72364435 by AkiLotus")
    129 
    130 **Source code in plain text**
    131 
    132 ```
    133 #include <bits/stdc++.h>
    134 using namespace std;
    135 
    136 int main() {
    137 	string s;
    138 	cin >> s;
    139 	vector<int> le, ri;
    140 	int l = 0, r = s.size() - 1;
    141 	while(l < r) {
    142 		while(l < s.size() && s[l] == ')')
    143 			l++;
    144 		while(r >= 0 && s[r] == '(')
    145 			r--;
    146 		if(l < s.size() && r >= 0 && l < r) {
    147 			le.push_back(l + 1);
    148 			ri.push_back(r + 1);
    149 			l++;
    150 			r--;
    151 		}
    152 	}
    153 	if(le.empty()) {
    154 		cout << "0\n";
    155 		return 0;
    156 	}
    157 	cout << "1\n";
    158 	cout << 2 * le.size() << '\n';
    159 	for(auto x : le)
    160 		cout << x << " ";
    161 	reverse(ri.begin(), ri.end());
    162 	for(auto x : ri)
    163 		cout << x << " ";
    164 	cout << '\n';
    165 }
    166 ```
    167 
    168 **Solution (Akikaze, Java 8)**
    169 
    170 Submission link: [72364561](/contest/1305/submission/72364561 "Submission 72364561 by AkiLotus")
    171 
    172 **Source code in plain text**
    173 
    174 ```
    175 import java.io.*;
    176 import java.util.*;
    177 
    178 public class JavAki {
    179 	public static Scanner sc = new Scanner(System.in);
    180 
    181 	public static String s;
    182 
    183 	public static void Input() {
    184 		s = sc.next();
    185 	}
    186 
    187 	public static void Solve() {
    188 		ArrayList<Integer> oList = new ArrayList<>();
    189 		ArrayList<Integer> cList = new ArrayList<>();
    190 		for (int i=0; i<s.length(); i++) {
    191 			if (s.charAt(i) == '(') oList.add(i);
    192 			if (s.charAt(i) == ')') cList.add(i);
    193 		}
    194 
    195 		ArrayList<Integer> removal = new ArrayList<>();
    196 		int oPtr = 0, cPtr = cList.size() - 1;
    197 		while (oPtr < oList.size() && cPtr >= 0) {
    198 			if (oList.get(oPtr) > cList.get(cPtr)) break;
    199 			removal.add(oList.get(oPtr)); removal.add(cList.get(cPtr));
    200 			oPtr++; cPtr--;
    201 		}
    202 
    203 		Collections.sort(removal);
    204 		if (removal.size() == 0) System.out.println(0);
    205 		else {
    206 			System.out.println(1); System.out.println(removal.size());
    207 			for (int x: removal) System.out.print((x+1) + " ");
    208 			System.out.println();
    209 		}
    210 	}
    211 
    212 	public static void main(String[] args) {
    213 		Input(); Solve();
    214 	}
    215 }
    216 ```
    217 
    218 **Solution (Akikaze, Python 3)**
    219 
    220 Submission link: [72364606](/contest/1305/submission/72364606 "Submission 72364606 by AkiLotus")
    221 
    222 **Source code in plain text**
    223 
    224 ```
    225 string = input()
    226 oList, cList = [], []
    227 for i in range(len(string)):
    228 	if string[i] == '(': oList.append(i)
    229 	if string[i] == ')': cList.append(i)
    230 
    231 oPtr, cPtr = 0, len(cList)-1
    232 removal = []
    233 while oPtr < len(oList) and cPtr >= 0:
    234 	if oList[oPtr] > cList[cPtr]: break
    235 	removal.append(oList[oPtr])
    236 	removal.append(cList[cPtr])
    237 	oPtr += 1
    238 	cPtr -= 1
    239 
    240 removal.sort()
    241 if len(removal) == 0: print(0)
    242 else: print('1\n{}\n{}'.format(len(removal), ' '.join([str(x+1) for x in removal])))
    243 ```
    244 
    245 ## [1305C - Kuroni and Impossible Calculation](/contest/1305/problem/C)
    246 
    247 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")  
    248 Development: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [Ari](/profile/Ari "International Master Ari")  
    249 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")
    250 
    251 **Tutorial**
    252 
    253 Tutorial is loading...
    254 
    255 **Solution (antontrygubO_o, C++)**
    256 
    257 Submission link: [72364777](/contest/1305/submission/72364777 "Submission 72364777 by AkiLotus")
    258 
    259 **Source code in plain text**
    260 
    261 ```
    262 #include <bits/stdc++.h>
    263 
    264 using namespace std;
    265 
    266 int p;
    267 
    268 int mul(int a, int b) {
    269     return (1LL * a * b) % p;
    270 }
    271 
    272 int sub(int a, int b) {
    273     int s = (a+p-b);
    274     if (s>=p) s-=p;
    275     return s;
    276 }
    277 
    278 int main() {
    279     ios_base::sync_with_stdio(0);
    280     cin.tie(nullptr);
    281 
    282     int n;
    283     cin>>n>>p;
    284     if (n>p) {cout<<0; return 0;}
    285     vector<int> a(n);
    286     for (int i = 0; i<n; i++) cin>>a[i];
    287     int res = 1;
    288     for (int i = 0; i<n; i++)
    289         for (int j = i+1; j<n; j++) res = mul(res, abs(a[i] - a[j])%p);
    290     cout<<res;
    291 }
    292 ```
    293 
    294 **Solution (Akikaze, Java 8)**
    295 
    296 Submission link: [72364959](/contest/1305/submission/72364959 "Submission 72364959 by AkiLotus")
    297 
    298 **Source code in plain text**
    299 
    300 ```
    301 import java.io.*;
    302 import java.util.*;
    303 
    304 public class JavAki {
    305 	public static Scanner sc = new Scanner(System.in);
    306 
    307 	public static int n, m;
    308 	public static int[] a;
    309 
    310 	public static void Input() {
    311 		n = sc.nextInt(); m = sc.nextInt();
    312 		a = new int[n];
    313 		for (int i=0; i<n; i++) a[i] = sc.nextInt();
    314 	}
    315 
    316 	public static void Solve() {
    317 		if (n > m) {System.out.println(0); return;}
    318 
    319 		int ans = 1;
    320 		for (int i=0; i<n; i++) {
    321 			for (int j=i+1; j<n; j++) {
    322 				ans = (int)(((long)ans * Math.abs(a[i] - a[j])) % m);
    323 			}
    324 		}
    325 		System.out.println(ans);
    326 	}
    327 
    328 	public static void main(String[] args) {
    329 		Input(); Solve();
    330 	}
    331 }
    332 ```
    333 
    334 **Solution (Akikaze, Python 3)**
    335 
    336 Submission link: [72365002](/contest/1305/submission/72365002 "Submission 72365002 by AkiLotus")
    337 
    338 **Source code in plain text**
    339 
    340 ```
    341 n, m = map(int, input().split())
    342 a = list(map(int, input().split()))
    343 
    344 if n > m: exit(print(0))
    345 
    346 ans = 1
    347 for i in range(n):
    348 	for j in range(i+1, n):
    349 		ans *= abs(a[i] - a[j])
    350 		ans %= m
    351 print(ans)
    352 ```
    353 
    354 ## [1305D - Kuroni and the Celebration](/contest/1305/problem/D)
    355 
    356 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    357 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj")  
    358 Editorialist: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")
    359 
    360 **Tutorial**
    361 
    362 Tutorial is loading...
    363 
    364 **Solution (Akikaze, C++)**
    365 
    366 Submission link: [72365359](/contest/1305/submission/72365359 "Submission 72365359 by AkiLotus")
    367 
    368 **Source code in plain text**
    369 
    370 ```
    371 #pragma GCC optimize("Ofast")
    372 
    373 #include <bits/stdc++.h>
    374 using namespace std;
    375 
    376 #define endl '\n'
    377 
    378 int n; vector<set<int>> adj;
    379 set<int> leafList;
    380 
    381 int ask(int u, int v) {
    382 	cout << "? " << u+1 << " " << v+1 << endl; cout.flush();
    383 	int w; cin >> w; assert(w != -1);
    384 	return (w - 1);
    385 }
    386 
    387 void answer(int r) {
    388 	cout << "! " << (r+1) << endl;
    389 	cout.flush(); exit(0);
    390 }
    391 
    392 void purge(int z, int last, int blockpoint) {
    393 	if (leafList.find(z) != leafList.end()) leafList.erase(z);
    394 
    395 	for (int t: adj[z]) {
    396 		if (t == last) continue;
    397 		if (t == blockpoint) adj[t].erase(z);
    398 		else if (adj[t].size() != 0) purge(t, z, blockpoint);
    399 	}
    400 
    401 	adj[z].clear();
    402 }
    403 
    404 void Input() {
    405 	cin >> n; adj.resize(n);
    406 	for (int i=1; i<n; i++) {
    407 		int x, y; cin >> x >> y; x--; y--;
    408 		adj[x].insert(y); adj[y].insert(x);
    409 	}
    410 }
    411 
    412 void Solve() {
    413 	for (int i=0; i<n; i++) {
    414 		if (adj[i].size() == 1) leafList.insert(i);
    415 	}
    416 
    417 	while (leafList.size() > 1) {
    418 		int u = *leafList.begin(); leafList.erase(u);
    419 		int v = *leafList.begin(); leafList.erase(v);
    420 		int w = ask(u, v);
    421 		if (w == u || w == v) answer(w);
    422 
    423 		purge(u, -1, w); purge(v, -1, w);
    424 		if (adj[w].size() <= 1) leafList.insert(w);
    425 	}
    426 
    427 	answer(*leafList.begin());
    428 }
    429 
    430 int main(int argc, char* argv[]) {
    431 	ios_base::sync_with_stdio(false);
    432 	Input(); Solve(); return 0;
    433 }
    434 ```
    435 
    436 **Solution (Akikaze, Java 8)**
    437 
    438 Submission link: [72365417](/contest/1305/submission/72365417 "Submission 72365417 by AkiLotus")
    439 
    440 **Source code in plain text**
    441 
    442 ```
    443 import java.io.*;
    444 import java.util.*;
    445 
    446 public class JavAki {
    447 	public static Scanner sc = new Scanner(System.in);
    448 
    449 	public static int n;
    450 	public static ArrayList<HashSet<Integer>> adj;
    451 	public static HashSet<Integer> leafList;
    452 
    453 	public static int ask(int u, int v) {
    454 		System.out.println("? " + (u+1) + " " + (v+1)); System.out.flush();
    455 		return (sc.nextInt() - 1);
    456 	}
    457 
    458 	public static void answer(int r) {
    459 		System.out.println("! " + (r+1)); System.out.flush();
    460 		System.exit(0);
    461 	}
    462 
    463 	public static void purge(int z, int last, int blockpoint) {
    464 		if (leafList.contains(z)) leafList.remove(z);
    465 
    466 		for (int t: adj.get(z)) {
    467 			if (t == last) continue;
    468 			if (t == blockpoint) adj.get(t).remove(z);
    469 			else if (adj.get(t).size() > 0) purge(t, z, blockpoint);
    470 		}
    471 
    472 		adj.get(z).clear();
    473 	}
    474 
    475 	public static void Input() {
    476 		n = sc.nextInt();
    477 		adj = new ArrayList<>();
    478 		for (int i=0; i<n; i++) adj.add(new HashSet<>());
    479 		for (int i=1; i<n; i++) {
    480 			int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
    481 			adj.get(x).add(y); adj.get(y).add(x);
    482 		}
    483 	}
    484 
    485 	public static void Solve() {
    486 		leafList = new HashSet<>();
    487 		for (int i=0; i<n; i++) {
    488 			if (adj.get(i).size() == 1) leafList.add(i);
    489 		}
    490 
    491 		while (leafList.size() > 1) {
    492 			int u = leafList.iterator().next(); leafList.remove(u);
    493 			int v = leafList.iterator().next(); leafList.remove(v);
    494 			int w = ask(u, v);
    495 			if (w == u || w == v) answer(w);
    496 
    497 			purge(u, -1, w); purge(v, -1, w);
    498 			if (adj.get(w).size() <= 1) leafList.add(w);
    499 		}
    500 
    501 		answer(leafList.iterator().next());
    502 	}
    503 
    504 	public static void main(String[] args) {
    505 		Input(); Solve();
    506 	}
    507 }
    508 ```
    509 
    510 **Solution (Akikaze, Python 3)**
    511 
    512 Submission link: [72365485](/contest/1305/submission/72365485 "Submission 72365485 by AkiLotus")
    513 
    514 **Source code in plain text**
    515 
    516 ```
    517 from sys import stdout
    518 
    519 def ask(u, v):
    520 	print('? {} {}'.format(u+1, v+1))
    521 	stdout.flush()
    522 	return (int(input()) - 1)
    523 
    524 def answer(r):
    525 	print('! {}'.format(r+1))
    526 	stdout.flush()
    527 	exit()
    528 
    529 n = int(input())
    530 adj = [{} for _ in range(n)]
    531 isLeaf = {}
    532 
    533 def purge(z, last, blockpoint):
    534 	if z in isLeaf: isLeaf.pop(z)
    535 
    536 	for t in adj[z].keys():
    537 		if t == last: continue
    538 		if t == blockpoint: adj[t].pop(z)
    539 		elif len(adj[t]) > 0: purge(t, z, blockpoint)
    540 	
    541 	adj[z].clear()
    542 
    543 for _ in range(n-1):
    544 	x, y = map(lambda s: int(s)-1, input().split())
    545 	adj[x][y] = True
    546 	adj[y][x] = True
    547 
    548 for i in range(n):
    549 	if len(adj[i]) == 1: isLeaf[i] = True
    550 
    551 while len(isLeaf) > 1:
    552 	taken = []
    553 	for key in isLeaf.keys():
    554 		taken.append(key)
    555 		if len(taken) == 2: break
    556 	
    557 	for key in taken: isLeaf.pop(key)
    558 	w = ask(taken[0], taken[1])
    559 
    560 	if w in taken: answer(w)
    561 	for key in taken: purge(key, -1, w)
    562 	if len(adj[w]) <= 1: isLeaf[w] = True
    563 
    564 for key in isLeaf.keys(): answer(key)
    565 ```
    566 
    567 ## [1305E - Kuroni and the Score Distribution](/contest/1305/problem/E)
    568 
    569 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")  
    570 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    571 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")
    572 
    573 **Tutorial**
    574 
    575 Tutorial is loading...
    576 
    577 **Solution (xuanquang1999, C++)**
    578 
    579 Submission link: [72365646](/contest/1305/submission/72365646 "Submission 72365646 by AkiLotus")
    580 
    581 **Source code in plain text**
    582 
    583 ```
    584 #include <bits/stdc++.h>
    585 
    586 using namespace std;
    587 
    588 int main() {
    589   int n, m;
    590   scanf("%d%d", &n, &m);
    591 
    592   vector<int> ans(n);
    593   vector<int> sumCnt(2 * n + 1, 0);
    594   int remain = m;
    595   
    596   int j;  
    597   for(j = 0; j < n; ++j) {    
    598     if (remain <= sumCnt[j + 1])
    599       break;
    600     remain -= sumCnt[j + 1];
    601     ans[j] = j+1;
    602     for(int i = 0; i < j; ++i)
    603       ++sumCnt[ans[i] + ans[j]];
    604   }
    605 
    606   if (j == n) {
    607     puts("-1");
    608     return 0;
    609   }
    610   
    611   int x = j+1;
    612   while (remain != sumCnt[x])
    613     ++x;
    614   ans[j] = x;
    615 
    616   int maxSum = (j == 0) ? ans[j] : (ans[j-1] + ans[j]);
    617   int cur = maxSum + 1;
    618   for(int i = j+1; i < n; ++i) {
    619     ans[i] = cur;
    620     cur += 2 * (maxSum + 1);
    621   }
    622 
    623   for(int i = 0; i < n; ++i)
    624     printf("%d ", ans[i]);
    625   puts("");
    626 
    627   return 0;
    628 }
    629 ```
    630 
    631 **Solution (Akikaze, Java 8)**
    632 
    633 Submission link: [72365683](/contest/1305/submission/72365683 "Submission 72365683 by AkiLotus")
    634 
    635 **Source code in plain text**
    636 
    637 ```
    638 import java.io.*;
    639 import java.util.*;
    640 
    641 public class JavAki {
    642 	public static Scanner sc = new Scanner(System.in);
    643 
    644 	public static int n, m;
    645 
    646 	public static void Input() {
    647 		n = sc.nextInt(); m = sc.nextInt();
    648 	}
    649 
    650 	public static void Solve() {
    651 		int count = 0;
    652 		ArrayList<Integer> numList = new ArrayList<>();
    653 		ArrayList<Integer> backdoor = new ArrayList<>();
    654 		for (int i=1; i<=n; i++) {
    655 			count += (i - 1) / 2;
    656 			numList.add(i);
    657 		}
    658 
    659 		if (count < m) {System.out.println("-1"); return;}
    660 
    661 		while (count > m) {
    662 			int lastpop = numList.remove(numList.size() - 1);
    663 			count -= (lastpop - 1) / 2;
    664 
    665 			if (count >= m) {
    666 				if (backdoor.size() == 0) backdoor.add(1000000000);
    667 				else backdoor.add(backdoor.get(backdoor.size() - 1) - (1 << 16));
    668 			}
    669 			else {
    670 				int gap = m - count;
    671 				backdoor.add(2 * (lastpop - gap) - 1);
    672 				count += gap;
    673 			}
    674 		}
    675 
    676 		while (backdoor.size() > 0) numList.add(backdoor.remove(backdoor.size() - 1));
    677 
    678 		for (int x: numList) System.out.print(x + " "); System.out.println();
    679 	}
    680 
    681 	public static void main(String[] args) {
    682 		Input(); Solve();
    683 	}
    684 }
    685 ```
    686 
    687 **Solution (Akikaze, Python 3)**
    688 
    689 Submission link: [72365705](/contest/1305/submission/72365705 "Submission 72365705 by AkiLotus")
    690 
    691 **Source code in plain text**
    692 
    693 ```
    694 n, m = map(int, input().split())
    695 
    696 numList = [x+1 for x in range(n)]
    697 backdoor = []
    698 
    699 count = sum([(i-1) // 2 for i in range(1, n+1)])
    700 
    701 if count < m: exit(print(-1))
    702 
    703 while count > m:
    704 	lastpop = numList.pop()
    705 	count -= (lastpop - 1) // 2
    706 
    707 	if count >= m:
    708 		if len(backdoor) == 0: backdoor.append(10 ** 9)
    709 		else: backdoor.append(backdoor[-1] - 2 ** 16)
    710 	else:
    711 		gap = m - count
    712 		backdoor.append(2 * (lastpop - gap) - 1)
    713 		count += gap
    714 
    715 while len(backdoor) > 0: numList.append(backdoor.pop())
    716 
    717 print(' '.join([str(x) for x in numList]))
    718 ```
    719 
    720 ## [1305F - Kuroni and the Punishment](/contest/1305/problem/F)
    721 
    722 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")  
    723 Development: [Ari](/profile/Ari "International Master Ari"), [265918](/profile/265918 "Candidate Master 265918"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
    724 Editorialist: [Ari](/profile/Ari "International Master Ari")
    725 
    726 **Tutorial**
    727 
    728 Tutorial is loading...
    729 
    730 **Solution (Kuroni, C++)**
    731 
    732 Submission link: [72365845](/contest/1305/submission/72365845 "Submission 72365845 by AkiLotus")
    733 
    734 **Source code in plain text**
    735 
    736 ```
    737 #include <bits/stdc++.h>
    738 using namespace std;
    739 
    740 const int N = 300005, MX = 1E6;
    741 const long long INF = 1E12;
    742 
    743 int n, ans = N;
    744 long long a[N];
    745 bool chk[MX];
    746 set<long long> can;
    747 vector<int> pr;
    748 mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    749 
    750 void init() {
    751     for (int i = 2; i < MX; i++) {
    752         if (!chk[i]) {
    753             pr.push_back(i);
    754             for (int j = i; j < MX; j += i) {
    755                 chk[j] = true;
    756             }
    757         }
    758     }
    759 }
    760 
    761 void add_prime(long long u) {
    762     for (int &v : pr) {
    763         if (u % v == 0) {
    764             can.insert(v);
    765             while (u % v == 0) {
    766                 u /= v;
    767             }
    768         }
    769     }
    770     if (u > 1) {
    771         can.insert(u);
    772     }
    773 }
    774 
    775 int solve(long long u) {
    776     long long ret = 0;
    777     for (int i = 1; i <= n; i++) {
    778         long long add = (a[i] < u ? u - a[i] : min(a[i] % u, u - a[i] % u));
    779         ret = min((long long) n, ret + add);
    780     }
    781     return ret;
    782 }
    783 
    784 int main() {
    785     ios_base::sync_with_stdio(false);
    786     cin.tie(nullptr);
    787     init();
    788     cin >> n;
    789     vector<int> per;
    790     for (int i = 1; i <= n; i++) {
    791         cin >> a[i];
    792         per.push_back(i);
    793     }
    794     shuffle(per.begin(), per.end(), mt);
    795     for (int i = 0; i < 100 && i < (int)per.size(); i++) {
    796         int u = per[i];
    797         add_prime(a[u]);
    798         add_prime(a[u] + 1);
    799         if (a[u] > 1) {
    800             add_prime(a[u] - 1);
    801         }
    802     }
    803     for (long long v : can) {
    804         ans = min(ans, solve(v));
    805     }
    806     cout << ans;
    807 }
    808 ```
    809 
    810 **Solution (Akikaze, Java 8)**
    811 
    812 Submission link: [72365871](/contest/1305/submission/72365871 "Submission 72365871 by AkiLotus")
    813 
    814 **Source code in plain text**
    815 
    816 ```
    817 import java.io.*;
    818 import java.util.*;
    819 
    820 public class JavAki {
    821 	public static Scanner sc = new Scanner(System.in);
    822 
    823 	public static int n;
    824 	public static long a[];
    825 	public static int iterationLimit = 8;
    826 
    827 	public static ArrayList<Integer> factorization(long x) {
    828 		ArrayList<Integer> primes = new ArrayList<>();
    829 		for (int i=2; i<=Math.sqrt(x); i++) {
    830 			if (x % i == 0) {
    831 				primes.add(i);
    832 				while (x % i == 0) x /= i;
    833 			}
    834 		}
    835 		if (x > 1 && x < Integer.MAX_VALUE) primes.add((int)x);
    836 		return primes;
    837 	}
    838 
    839 	public static long solve_with_fixed_gcd(int gcd) {
    840 		long result = 0;
    841 		for (int i=0; i<n; i++) {
    842 			if (a[i] < gcd) result += (gcd - a[i]);
    843 			else {
    844 				int remainder = (int)(a[i] % gcd);
    845 				result += Math.min(remainder, gcd - remainder);
    846 			}
    847 		}
    848 		return result;
    849 	}
    850 
    851 	public static void Input() {
    852 		n = sc.nextInt(); a = new long[n];
    853 		for (int i=0; i<n; i++) a[i] = sc.nextLong();
    854 	}
    855 
    856 	public static void Solve() {
    857 		ArrayList<Integer> iterations = new ArrayList<>();
    858 		for (int i=0; i<n; i++) iterations.add(i);
    859 		Collections.shuffle(iterations);
    860 		while (iterations.size() > iterationLimit) iterations.remove(iterations.size() - 1);
    861 
    862 		long answer = Long.MAX_VALUE;
    863 		HashSet<Integer> prime_list = new HashSet<>();
    864 		for (int index: iterations) {
    865 			for (int x=-1; x<=+1; x++) {
    866 				ArrayList<Integer> tmp = factorization(a[index] - x);
    867 				for (int z: tmp) prime_list.add(z);
    868 			}
    869 		}
    870 
    871 		for (int prime: prime_list) {
    872 			answer = Math.min(answer, solve_with_fixed_gcd(prime));
    873 			if (answer == 0) break;
    874 		}
    875 		System.out.println(answer);
    876 	}
    877 
    878 	public static void main(String[] args) {
    879 		Input(); Solve();
    880 	}
    881 }
    882 ```
    883 
    884 **Solution (Akikaze, PyPy 3)**
    885 
    886 Submission link: [72365967](/contest/1305/submission/72365967 "Submission 72365967 by AkiLotus")
    887 
    888 **Source code in plain text**
    889 
    890 ```
    891 import random
    892 
    893 n = int(input())
    894 a = list(map(int, input().split()))
    895 
    896 limit = min(8, n)
    897 iterations = [x for x in range(n)]
    898 random.shuffle(iterations)
    899 iterations = iterations[:limit]
    900 
    901 def factorization(x):
    902 	primes = []
    903 	i = 2
    904 	while i * i <= x:
    905 		if x % i == 0:
    906 			primes.append(i)
    907 			while x % i == 0: x //= i
    908 		i = i + 1
    909 	if x > 1: primes.append(x)
    910 	return primes
    911 
    912 def solve_with_fixed_gcd(arr, gcd):
    913 	result = 0
    914 	for x in arr:
    915 		if x < gcd: result += (gcd - x)
    916 		else:
    917 			remainder = x % gcd
    918 			result += min(remainder, gcd - remainder)
    919 	return result
    920 
    921 answer = float("inf")
    922 prime_list = set()
    923 for index in iterations:
    924 	for x in range(-1, 2):
    925 		tmp = factorization(a[index]-x)
    926 		for z in tmp: prime_list.add(z)
    927 
    928 for prime in prime_list:
    929 	answer = min(answer, solve_with_fixed_gcd(a, prime))
    930 	if answer == 0: break
    931 
    932 print(answer)
    933 ```
    934 
    935 ## [1305G - Kuroni and Antihype](/contest/1305/problem/G)
    936 
    937 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")  
    938 Development: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")  
    939 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")
    940 
    941 **Tutorial**
    942 
    943 Tutorial is loading...
    944 
    945 **Solution (Approach #1) (kefaa2, C++)**
    946 
    947 Submission link: [72366230](/contest/1305/submission/72366230 "Submission 72366230 by AkiLotus")
    948 
    949 **Source code in plain text**
    950 
    951 ```
    952 #ifdef DEBUG
    953 #define _GLIBCXX_DEBUG
    954 #endif
    955 //#pragma GCC optimize("O3")
    956 #include <bits/stdc++.h>
    957 using namespace std;
    958 typedef long double ld;
    959 typedef long long ll;
    960 int n;
    961 const int maxN = (1 << 18) + 2;
    962 int a[maxN];
    963 ll ans = 0;
    964 int p[maxN];
    965 pair < int, int > best[maxN][2];
    966 pair < int, int > largest[maxN];
    967 int get(int a) {
    968     if (a == p[a]) return a;
    969     return p[a] = get(p[a]);
    970 }
    971 mt19937 rnd(228);
    972 bool unite(int a, int b) {
    973     a = get(a);
    974     b = get(b);
    975     if (a == b) return false;
    976     if (rnd() & 1) swap(a, b);
    977     p[a] = b;
    978     return true;
    979 }
    980 int main() {
    981     ios_base::sync_with_stdio(false);
    982     cin.tie(nullptr);
    983     //freopen("input.txt", "r", stdin);
    984     cin >> n;
    985     //n = 2e5;
    986     for (int i = 1; i <= n; i++) {
    987         cin >> a[i];
    988         //a[i] = i;
    989         ans -= a[i];
    990         p[i] = i;
    991     }
    992     int cmp = n + 1;
    993     while (cmp > 1) {
    994         for (int i = 0; i < (1 << 18); i++) {
    995             best[i][0] = {-1, -1};
    996             best[i][1] = {-1, -1};
    997         }
    998         for (int j = 0; j <= n; j++) {
    999             pair < int, int > f = {a[j], get(j)};
   1000             if (best[a[j]][0] < f) {
   1001                 if (best[j][0].second != f.second) best[a[j]][1] = best[a[j]][0];
   1002                 best[a[j]][0] = f;
   1003             }
   1004             else if (best[a[j]][1] < f && best[a[j]][0].second != f.second) {
   1005                 best[a[j]][1] = f;
   1006             }
   1007         }
   1008         for (int bit = 0; bit < 18; bit++) {
   1009             for (int mask = 0; mask < (1 << 18); mask++) {
   1010                 if (mask & (1 << bit)) {
   1011                     for (int iter = 0; iter < 2; iter++) {
   1012                         if (best[mask][0] < best[mask ^ (1 << bit)][iter]) {
   1013                             if (best[mask][0].second != best[mask ^ (1 << bit)][iter].second) best[mask][1] = best[mask][0];
   1014                             best[mask][0] = best[mask ^ (1 << bit)][iter];
   1015                         }
   1016                         else if (best[mask][1] < best[mask ^ (1 << bit)][iter] && best[mask][0].second != best[mask ^ (1 << bit)][iter].second) {
   1017                             best[mask][1] = best[mask ^ (1 << bit)][iter];
   1018                         }
   1019                     }
   1020                 }
   1021             }
   1022         }
   1023         int all = (1 << 18) - 1;
   1024         for (int i = 0; i <= n; i++) {
   1025             largest[i] = {-1, -1};
   1026         }
   1027         for (int i = 0; i <= n; i++) {
   1028             int where = (all ^ a[i]);
   1029             int his_id = get(i);
   1030             if (best[where][0].second != -1 && best[where][0].second != his_id) {
   1031                 largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][0].first, best[where][0].second));
   1032             }
   1033             else if (best[where][1].second != -1 && best[where][1].second != his_id) {
   1034                 largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][1].first, best[where][1].second));
   1035             }
   1036         }
   1037         for (int i = 0; i <= n; i++) {
   1038             if (p[i] != i) continue;
   1039             if (unite(i, largest[i].second)) {
   1040                 cmp--;
   1041                 ans += largest[i].first;
   1042             }
   1043         }
   1044     }
   1045     cout << ans;
   1046     return 0;
   1047 }
   1048 ```
   1049 
   1050 **Solution (Approach #2) (Kuroni, C++)**
   1051 
   1052 Submission link: [72366838](/contest/1305/submission/72366838 "Submission 72366838 by AkiLotus")
   1053 
   1054 **Source code in plain text**
   1055 
   1056 ```
   1057 #include <bits/stdc++.h>
   1058 using namespace std;
   1059 
   1060 const int N = 1 << 18;
   1061 
   1062 int n, u, cnt[N];
   1063 long long ans = 0;
   1064 
   1065 struct dsu {
   1066     int dsu[N];
   1067 
   1068     void init() {
   1069         fill(dsu, dsu + N, -1);
   1070     }
   1071 
   1072     int trace(int u) {
   1073         return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
   1074     }
   1075 
   1076     int connect(int u, int v) {
   1077         if ((u = trace(u)) == (v = trace(v))) {
   1078             return 0;
   1079         }
   1080         if (dsu[u] > dsu[v]) {
   1081             swap(u, v);
   1082         }
   1083         int ans = (dsu[u] == -1 ? cnt[u] : 1) + (dsu[v] == -1 ? cnt[v] : 1) - 1;
   1084         dsu[u] += dsu[v];
   1085         dsu[v] = u;
   1086         return ans;
   1087     }
   1088 } dsu;
   1089 
   1090 int main() {
   1091     ios_base::sync_with_stdio(false);
   1092     cin.tie(nullptr);
   1093     cin >> n;
   1094     for (int i = 0; i < n; i++) {
   1095         cin >> u;
   1096         cnt[u]++;
   1097         ans -= u;
   1098     }
   1099     cnt[0]++;
   1100     dsu.init();
   1101     for (int sum = N - 1; sum >= 0; sum--) {
   1102         for (int u = sum; u > 0; (--u) &= sum) {
   1103             int v = sum ^ u;
   1104             if (cnt[u] > 0 && cnt[v] > 0) {
   1105                 ans += 1LL * sum * dsu.connect(u, v);
   1106             }
   1107         }
   1108     }
   1109     cout << ans;
   1110 }
   1111 ```
   1112 
   1113 **Solution (Approach #2) (pajenegod, PyPy2)**
   1114 
   1115 Submission link: [72758499](/contest/1305/submission/72758499 "Submission 72758499 by pajenegod")
   1116 
   1117 **Source code in plain text**
   1118 
   1119 ```
   1120 import sys
   1121 range = xrange
   1122 input = raw_input
   1123 
   1124 n = int(input())
   1125 A = [int(x) for x in input().split()]
   1126 
   1127 m = 2**18
   1128 count = [0]*m
   1129 for a in A:
   1130     count[a] += 1
   1131 count[0] += 1
   1132 
   1133 # Using dsu with O(1) lookup and O(log(n)) merge
   1134 owner = list(range(m))
   1135 sets = [[i] for i in range(m)]
   1136  
   1137 total = 0
   1138 for profit in reversed(range(m)):
   1139     a = profit
   1140     b = a ^ profit
   1141     while a > b:
   1142         if count[a] and count[b] and owner[a] != owner[b]:
   1143             total += (count[a] + count[b] - 1) * profit
   1144             count[a] = 1
   1145             count[b] = 1
   1146             
   1147             small = owner[a]
   1148             big = owner[b]
   1149             if len(sets[small]) > len(sets[big]):
   1150                 small, big = big, small
   1151             for c in sets[small]:
   1152                 owner[c] = big
   1153             sets[big] += sets[small]
   1154         a = (a - 1) & profit
   1155         b = a ^ profit
   1156 print total - sum(A)
   1157 ```
   1158 
   1159 ## [1305H - Kuroni the Private Tutor](/contest/1305/problem/H)
   1160 
   1161 Author: [zscoder](/profile/zscoder "Grandmaster zscoder")  
   1162 Development: [zscoder](/profile/zscoder "Grandmaster zscoder"), [ngfam](/profile/ngfam "Grandmaster ngfam"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")  
   1163 Editorialist: [zscoder](/profile/zscoder "Grandmaster zscoder")
   1164 
   1165 **Tutorial**
   1166 
   1167 Tutorial is loading...
   1168 
   1169 **Solution (zscoder, C++)**
   1170 
   1171 Submission link: [72366397](/contest/1305/submission/72366397 "Submission 72366397 by AkiLotus")
   1172 
   1173 **Source code in plain text**
   1174 
   1175 ```
   1176 #include <bits/stdc++.h>
   1177 #include <ext/pb_ds/assoc_container.hpp>
   1178 #include <ext/pb_ds/tree_policy.hpp>
   1179  
   1180 using namespace std;
   1181 using namespace __gnu_pbds;
   1182  
   1183 #define fi first
   1184 #define se second
   1185 #define mp make_pair
   1186 #define pb push_back
   1187 #define fbo find_by_order
   1188 #define ook order_of_key
   1189  
   1190 typedef long long ll;
   1191 typedef pair<int,int> ii;
   1192 typedef vector<ll> vi;
   1193 typedef long double ld; 
   1194 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
   1195 
   1196 const int N = 150000; //number of problems
   1197 const int M = 150000; //number of students
   1198 
   1199 int L[N+10];
   1200 int R[N+10];
   1201 int a[N+10]; //array of fixed score
   1202 ll T; 
   1203 int n,m; 
   1204 
   1205 void read()
   1206 {
   1207 	cin>>n>>m;
   1208 	for(int i=0;i<n;i++) //problem score
   1209 	{
   1210 		cin>>L[i]>>R[i];
   1211 	}
   1212 	for(int i=0;i<m;i++) a[i]=-1;
   1213 	int q; cin>>q;
   1214 	for(int i=0;i<q;i++)
   1215 	{
   1216 		int rk, sc; cin>>rk>>sc;
   1217 		a[m-rk] = sc;
   1218 	}
   1219 	cin>>T; //total score	
   1220 }
   1221 
   1222 vector<ll> sortedL,sortedR;
   1223 
   1224 struct ConvexHull 
   1225 {
   1226     struct Line 
   1227     {
   1228         ll m, c;
   1229 
   1230         Line (ll _m, ll _c) : m(_m), c(_c) {}
   1231 
   1232         ll pass(ll x) {
   1233             return m * x + c;
   1234         }
   1235     };
   1236     deque<Line> d;
   1237     bool irrelevant(Line Z) 
   1238     {
   1239         if (int(d.size()) < 2) return false;
   1240     
   1241         Line X = d[int(d.size())-2], Y = d[int(d.size())-1];
   1242 
   1243         return (X.c - Z.c) * (Y.m - X.m) <= (X.c - Y.c) * (Z.m - X.m);
   1244     }
   1245     void push_line(ll m, ll c) 
   1246     {
   1247         Line l = Line(m,c);
   1248         while (irrelevant(l)) d.pop_back();
   1249         d.push_back(l);
   1250     }
   1251     ll query(ll x) {
   1252         while (int(d.size()) > 1 && (d[0].c - d[1].c <= x * (d[1].m - d[0].m))) d.pop_front();
   1253         return d.front().pass(x);
   1254     }
   1255 };
   1256 
   1257 bool check_naive(vector<int> b) //check if your assignment is valid
   1258 {
   1259 	ll sumB = 0;
   1260 	ll sumL = 0;
   1261 	sort(b.begin(),b.end());
   1262 	for(int i=0;i<b.size();i++)
   1263 	{
   1264 		sumB+=b[i];
   1265 		if(a[i]!=-1) assert(a[i]==b[i]);
   1266 		if(i>0) assert(b[i]>=b[i-1]);
   1267 	}
   1268 	for(int i=0;i<n;i++) sumL+=L[i];
   1269 	assert(int(b.size())==m&&sumB==T);
   1270 	ll cursum=0;
   1271 	for(int i=0;i<=m;i++)
   1272 	{
   1273 		for(int j=0;j<=n;j++)
   1274 		{
   1275 			ll s1 = sortedR[j]+cursum+(n-j)*1LL*(m-i);
   1276 			ll s2 = sortedL[j]+cursum+(n-j)*1LL*(m-i);
   1277 			if(s1<sumB||s2<sumL) return false;
   1278 		}
   1279 		if(i<m) cursum+=b[i];
   1280 	}
   1281 	return true;
   1282 }
   1283 
   1284 bool check(vector<int> b) //check if your assignment is valid
   1285 {
   1286 	ll sumB = 0;
   1287 	ll sumL = 0;
   1288 	sort(b.begin(),b.end());
   1289 	for(int i=0;i<b.size();i++)
   1290 	{
   1291 		sumB+=b[i];
   1292 		if(a[i]!=-1) assert(a[i]==b[i]);
   1293 		if(i>0) assert(b[i]>=b[i-1]);
   1294 	}
   1295 	for(int i=0;i<n;i++) sumL+=L[i];
   1296 	assert(int(b.size())==m&&sumB==T);
   1297 	ll cursum=0;
   1298 	ConvexHull ch1,ch2;
   1299 	for(int j=n;j>=0;j--)
   1300 	{
   1301 		ch1.push_line(n-j,-sortedR[j]+j*1LL*m);
   1302 		ch2.push_line(n-j,-sortedL[j]+j*1LL*m);
   1303 	}
   1304 	for(int i=0;i<=m;i++)
   1305 	{
   1306 		ll v1 = -ch1.query(i);
   1307 		ll v2 = -ch2.query(i);
   1308 		if(v1<sumB-(cursum+n*1LL*m)||v2<sumL-(cursum+n*1LL*m)) return false;
   1309 		if(i<m) cursum+=b[i];
   1310 	}
   1311 	return true;
   1312 }
   1313 
   1314 void greedyrange(vector<int> &v, int l, int r, int ub, ll &S) 
   1315 {
   1316 	if(S<=0) return ;
   1317 	ll ext = 0;
   1318 	for(int i=l;i<=r;i++)
   1319 	{
   1320 		ext+=ub-v[i];
   1321 	}
   1322 	if(ext<=S)
   1323 	{
   1324 		S-=ext;
   1325 		for(int i=l;i<=r;i++)
   1326 		{
   1327 			v[i]=ub;
   1328 		}
   1329 		return ;
   1330 	}
   1331 	deque<ii> dq; 
   1332 	for(int i=l;i<=r;i++) 
   1333 	{
   1334 		if(!dq.empty()&&dq.back().fi==v[i])
   1335 		{
   1336 			dq.back().se++;
   1337 		}
   1338 		else
   1339 		{
   1340 			dq.pb({v[i],1});
   1341 		}
   1342 	}
   1343 	while(S>0&&dq.size()>1)
   1344 	{
   1345 		int L = dq[0].fi; int cnt = dq[0].se;
   1346 		int R = dq[1].fi;
   1347 		//I have (R-L)*cnt before absolute merge
   1348 		if((R-L)*1LL*cnt<=S)
   1349 		{
   1350 			S-=(R-L)*1LL*cnt;
   1351 			dq[1].se+=cnt;
   1352 			dq.pop_front();
   1353 			continue;
   1354 		}
   1355 		//not enough space liao
   1356 		ll q = S/cnt;
   1357 		ll rem = S%cnt;
   1358 		dq[0].fi+=q;
   1359 		if(rem>0)
   1360 		{
   1361 			ii tmp = dq.front();
   1362 			dq.pop_front();
   1363 			dq.push_front({rem,tmp.fi+1});
   1364 			dq.push_front({cnt-rem,tmp.fi});
   1365 		}
   1366 		S=0;
   1367 		break;
   1368 	}
   1369 	//S>0
   1370 	if(S>0)
   1371 	{
   1372 		assert(int(dq.size())==1);
   1373 		ll q = S/(r-l+1);
   1374 		ll rem = S%(r-l+1);
   1375 		for(int i=l;i<=r;i++)
   1376 		{
   1377 			v[i]=dq[0].fi+q;
   1378 		}
   1379 		int ptr=r;
   1380 		for(int i=0;i<rem;i++)
   1381 		{
   1382 			v[ptr--]++;
   1383 		}
   1384 		S=0;
   1385 	}
   1386 	else
   1387 	{
   1388 		int ptr=l;
   1389 		for(ii x:dq)
   1390 		{
   1391 			for(int j=0;j<x.se;j++) v[ptr++]=x.fi;
   1392 		}
   1393 	}
   1394 }
   1395 
   1396 void greedy(vector<int> &v, ll &S)
   1397 {
   1398 	if(S<=0) return ;
   1399 	vi ans;
   1400 	vector<ii> ranges;
   1401 	int l=0;
   1402 	for(int i=0;i<m;i++)
   1403 	{
   1404 		if(a[i]==-1) continue;
   1405 		if(l<=i-1)
   1406 		{
   1407 			ranges.pb({l,i-1});
   1408 		}
   1409 		l=i+1;
   1410 	}
   1411 	if(l<m) ranges.pb({l,m-1});
   1412 	for(ii x:ranges)
   1413 	{
   1414 		int r=x.se;
   1415 		int ub = n;
   1416 		if(r+1<m&&a[r+1]!=-1) ub=a[r+1];
   1417 		greedyrange(v,x.fi,x.se,ub,S);
   1418 	}
   1419 }
   1420 
   1421 ii solve_full()
   1422 {
   1423 	sortedL.clear(); sortedR.clear();
   1424 	sortedL.pb(0); sortedR.pb(0);
   1425 	for(int i=0;i<n;i++)
   1426 	{
   1427 		sortedL.pb(L[i]);
   1428 		sortedR.pb(R[i]);
   1429 	}
   1430 	sort(sortedL.begin(),sortedL.end());
   1431 	sort(sortedR.begin(),sortedR.end());
   1432 	for(int i=1;i<=n;i++)
   1433 	{
   1434 		sortedL[i]+=sortedL[i-1];
   1435 		sortedR[i]+=sortedR[i-1];
   1436 	}
   1437 	//at least k people tie for first?
   1438 	int lo = 1; int hi = m; 
   1439 	int anstie = -1;
   1440 	int ansm = 0;
   1441 	vector<int> testb;
   1442 	vi ori(m,-1);
   1443 	while(lo<=hi)
   1444 	{
   1445 		int mid=(lo+hi)>>1;
   1446 		vector<int> b;
   1447 		int curmin=0;
   1448 		ll cursum=0;
   1449 		for(int i=0;i<m;i++)
   1450 		{
   1451 			if(a[i]!=-1) curmin=a[i];
   1452 			b.pb(curmin);
   1453 			cursum+=b[i];
   1454 		}
   1455 		//left T - cursum stuff to add :(
   1456 		//fix the maximum M
   1457 		bool pos=0;
   1458 		int forcedM=-1;
   1459 		for(int j=m-mid;j<m;j++)
   1460 		{
   1461 			if(a[j]>=0)
   1462 			{
   1463 				if(forcedM>=0&&forcedM!=a[j]) forcedM=-2;
   1464 				forcedM = a[j];
   1465 			}
   1466 		}
   1467 		if(forcedM>=-1)
   1468 		{
   1469 			int L2 = curmin; int R2 = n;
   1470 			if(forcedM>=0) L2=R2=forcedM;
   1471 			//otherwise L2 is the smallest d+curmin such that there EXIST a good covering
   1472 			if(forcedM<0)
   1473 			{
   1474 				int lo2 = curmin; int hi2 = max(0LL,min(ll(n),(T-cursum)/mid+curmin)); //add to everyone i guess
   1475 				L2=int(1e9);
   1476 				while(lo2<=hi2)
   1477 				{
   1478 					int mid2=(lo2+hi2)>>1;
   1479 					vector<int> nwb = b;
   1480 					ll rem = T - cursum;
   1481 					int M = mid2;
   1482 					for(int j=m-mid;j<m;j++)
   1483 					{
   1484 						rem+=b[j];
   1485 						rem-=M;
   1486 						nwb[j]=M;
   1487 						if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
   1488 						ori[j]=a[j];
   1489 						a[j]=M;
   1490 					}
   1491 					greedy(nwb, rem);
   1492 					for(int j=m-mid;j<m;j++)
   1493 					{
   1494 						a[j]=ori[j];
   1495 					}
   1496 					if(rem==0)
   1497 					{
   1498 						hi2=mid2-1;
   1499 						L2=mid2;
   1500 					}
   1501 					else 
   1502 					{
   1503 						lo2=mid2+1;
   1504 					}
   1505 				}
   1506 			}			
   1507 			//how to figure out L2 otherwise!?
   1508 			while(L2<=R2)
   1509 			{
   1510 				int M = (L2+R2)>>1;
   1511 				vector<int> nwb = b;
   1512 				ll rem = T - cursum;
   1513 				for(int j=m-mid;j<m;j++)
   1514 				{
   1515 					rem+=b[j];
   1516 					rem-=M;
   1517 					nwb[j]=M;
   1518 					if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
   1519 					ori[j]=a[j];
   1520 					a[j]=M;
   1521 				}
   1522 				greedy(nwb, rem);
   1523 				if(rem==0&&check(nwb))
   1524 				{
   1525 					testb=nwb; ansm=M;
   1526 					pos=1; L2=M+1;
   1527 				}
   1528 				else
   1529 				{
   1530 					R2=M-1;
   1531 				}
   1532 				for(int j=m-mid;j<m;j++)
   1533 				{
   1534 					a[j]=ori[j];
   1535 				}
   1536 			}
   1537 		}
   1538 		if(pos)
   1539 		{
   1540 			anstie=mid;
   1541 			lo=mid+1;
   1542 		}
   1543 		else hi=mid-1;
   1544 	}
   1545 	if(anstie==-1)
   1546 	{
   1547 		return {-1,-1};
   1548 	}
   1549 	return {anstie,ansm};
   1550 }
   1551 
   1552 int main()
   1553 {
   1554 	ios_base::sync_with_stdio(0); cin.tie(0);
   1555 	//freopen("student-scores.in","r",stdin);
   1556 	read();
   1557 	ii sol2 = solve_full();
   1558 	cout<<sol2.fi<<' '<<sol2.se<<'\n';
   1559 }
   1560 ```