codeforces-scrape

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

1837.md (7731B)


      1 Source: https://codeforces.com/blog/entry/116752
      2 
      3 [1837A - Grasshopper on a Line](/contest/1837/problem/A "Educational Codeforces Round 149 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	x, k = map(int, input().split())
     16 	if x % k != 0:
     17 		print(1)
     18 		print(x)
     19 	else:
     20 		print(2)
     21 		print(1, x - 1)
     22 ```
     23 
     24 [1837B - Comparison String](/contest/1837/problem/B "Educational Codeforces Round 149 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (BledDest)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36  
     37 using namespace std;
     38 
     39 int main()
     40 {
     41     ios_base::sync_with_stdio(0);
     42     cin.tie(0);
     43     int t;
     44     cin >> t;
     45     for(int i = 0; i < t; i++)
     46     {
     47         int n;
     48         cin >> n;
     49         string s;
     50         cin >> s;
     51         int ans = 1, cur = 1;
     52         for(int i = 1; i < n; i++)
     53         {
     54             if(s[i] != s[i - 1]) cur = 1;
     55             else cur++;
     56             ans = max(ans, cur);
     57         }
     58         cout << ans + 1 << endl;
     59     }    
     60 }
     61 ```
     62 
     63 [1837C - Best Binary String](/contest/1837/problem/C "Educational Codeforces Round 149 (Rated for Div. 2)")
     64 
     65 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution (Neon)**
     72 
     73 ```
     74 #include <bits/stdc++.h>
     75 
     76 using namespace std;
     77 
     78 int main() {
     79   ios::sync_with_stdio(false); cin.tie(0);
     80   int t;
     81   cin >> t;
     82   while (t--) {
     83     string s;
     84     cin >> s;
     85     char x = '0';
     86     for (auto& c : s) {
     87       if (c == '?') c = x;
     88       x = c;
     89     }
     90     cout << s << '\n';
     91   }
     92 }
     93 ```
     94 
     95 [1837D - Bracket Coloring](/contest/1837/problem/D "Educational Codeforces Round 149 (Rated for Div. 2)")
     96 
     97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Solution (BledDest)**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107  
    108 using namespace std;
    109 
    110 int main()
    111 {
    112     ios_base::sync_with_stdio(0);
    113     cin.tie(0);
    114     int t;
    115     cin >> t;
    116     for(int i = 0; i < t; i++)
    117     {
    118         int n;
    119         cin >> n;
    120         string s;
    121         cin >> s;
    122         vector<int> bal(n + 1);
    123         for(int j = 0; j < n; j++)
    124             if(s[j] == '(')
    125                 bal[j + 1] = bal[j] + 1;
    126             else
    127                 bal[j + 1] = bal[j] - 1;
    128 
    129         if(bal.back() != 0)
    130             cout << -1 << endl;
    131         else
    132         {
    133             if(*min_element(bal.begin(), bal.end()) == 0 || *max_element(bal.begin(), bal.end()) == 0)
    134             {
    135                 cout << 1 << endl;
    136                 for(int j = 0; j < n; j++)
    137                 {
    138                     if(j) cout << " ";
    139                     cout << 1;
    140                 }
    141                 cout << endl;
    142             }
    143             else
    144             {
    145                 cout << 2 << endl;
    146                 vector<int> ans;
    147                 int cur = 0;
    148                 while(cur < n)
    149                 {
    150                     int w = (s[cur] == '(' ? 1 : 2);
    151                     do
    152                     {
    153                         cur++;
    154                         ans.push_back(w);
    155                     }
    156                     while(bal[cur] != 0);
    157                 }
    158                 for(int j = 0; j < n; j++)
    159                 {
    160                     if(j) cout << " ";
    161                     cout << ans[j];
    162                 }
    163                 cout << endl;
    164             }
    165         }
    166     }    
    167 }
    168 ```
    169 
    170 [1837E - Playoff Fixing](/contest/1837/problem/E "Educational Codeforces Round 149 (Rated for Div. 2)")
    171 
    172 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution (awoo)**
    179 
    180 ```
    181 #include <bits/stdc++.h>
    182 
    183 #define forn(i, n) for (int i = 0; i < int(n); i++)
    184 
    185 using namespace std;
    186 
    187 const int MOD = 998244353;
    188 
    189 int main() {
    190 	int k;
    191 	scanf("%d", &k);
    192 	vector<int> a(1 << k);
    193 	forn(i, 1 << k){
    194 		scanf("%d", &a[i]);
    195 		if (a[i] != -1) --a[i];
    196 	}
    197 	int ans = 1;
    198 	for (int st = k - 1; st >= 0; --st){
    199 		int big = 1 << st, fr = 0;
    200 		vector<int> na(1 << st);
    201 		forn(i, 1 << st){
    202 			int mn = min(a[2 * i], a[2 * i + 1]);
    203 			int mx = max(a[2 * i], a[2 * i + 1]);
    204 			if (mn == -1){
    205 				if (mx >= (1 << st)){
    206 					--big;
    207 					na[i] = -1;
    208 				}
    209 				else if (mx != -1){
    210 					na[i] = mx;
    211 				}
    212 				else{
    213 					na[i] = -1;
    214 					++fr;
    215 				}
    216 				continue;
    217 			}
    218 			if ((a[2 * i] < (1 << st)) == (a[2 * i + 1] < (1 << st))){
    219 				puts("0");
    220 				return 0;
    221 			}
    222 			na[i] = mn;
    223 			--big;
    224 		}
    225 		forn(_, fr) ans = ans * 2ll % MOD;
    226 		for (int i = 1; i <= big; ++i) ans = ans * 1ll * i % MOD;
    227 		a = na;
    228 	}
    229 	printf("%d\n", ans);
    230 }
    231 ```
    232 
    233 [1837F - Editorial for Two](/contest/1837/problem/F "Educational Codeforces Round 149 (Rated for Div. 2)")
    234 
    235 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    236 
    237 **Tutorial**
    238 
    239 Tutorial is loading...
    240 
    241 **Solution 1 (awoo)**
    242 
    243 ```
    244 #include <bits/stdc++.h>
    245 
    246 #define forn(i, n) for (int i = 0; i < int(n); i++)
    247 
    248 using namespace std;
    249 
    250 int main() {
    251 	int t;
    252 	scanf("%d", &t);
    253 	while (t--){
    254 		int n, k;
    255 		scanf("%d%d", &n, &k);
    256 		vector<int> a(n);
    257 		forn(i, n) scanf("%d", &a[i]);
    258 		
    259 		vector<int> pr(n + 1), su(n + 1);
    260 		auto check = [&](long long x){
    261 			forn(_, 2){
    262 				priority_queue<int> cur;
    263 				pr[0] = 0;
    264 				long long cursum = 0;
    265 				forn(i, n){
    266 					cur.push(a[i]);
    267 					cursum += a[i];
    268 					while (cursum > x){
    269 						cursum -= cur.top();
    270 						cur.pop();
    271 					}
    272 					pr[i + 1] = cur.size();
    273 				}
    274 				reverse(a.begin(), a.end());
    275 				swap(pr, su);
    276 			}
    277 			reverse(su.begin(), su.end());
    278 			forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
    279 			return false;
    280 		};
    281 		
    282 		long long l = 1, r = accumulate(a.begin(), a.end(), 0ll);
    283 		long long res = 0;
    284 		while (l <= r){
    285 			long long m = (l + r) / 2;
    286 			if (check(m)){
    287 				res = m;
    288 				r = m - 1;
    289 			}
    290 			else{
    291 				l = m + 1;
    292 			}
    293 		}
    294 		printf("%lld\n", res);
    295 	}
    296 }
    297 ```
    298 
    299 **Solution 2 (awoo)**
    300 
    301 ```
    302 #include <bits/stdc++.h>
    303 
    304 #define forn(i, n) for (int i = 0; i < int(n); i++)
    305 
    306 using namespace std;
    307 
    308 int main() {
    309 	int t;
    310 	scanf("%d", &t);
    311 	while (t--){
    312 		int n, k;
    313 		scanf("%d%d", &n, &k);
    314 		vector<int> a(n);
    315 		forn(i, n) scanf("%d", &a[i]);
    316 		vector<pair<int, int>> xs(n);
    317 		forn(i, n) xs[i] = {a[i], i};
    318 		sort(xs.begin(), xs.end());
    319 		forn(i, n) a[i] = lower_bound(xs.begin(), xs.end(), make_pair(a[i], i)) - xs.begin();
    320 		
    321 		vector<int> lstpr(n), lstsu(n);
    322 		forn(_, 2){
    323 			set<int> cur;
    324 			forn(i, n){
    325 				auto it = cur.insert(a[i]).first;
    326 				if (it == cur.begin())
    327 					lstpr[i] = n;
    328 				else
    329 					lstpr[i] = *(--it);
    330 			}
    331 			swap(lstpr, lstsu);
    332 			reverse(a.begin(), a.end());
    333 		}
    334 		
    335 		vector<int> pr(n + 1), su(n + 1);
    336 		vector<int> prv(n + 2), nxt(n + 2);
    337 		
    338 		auto check = [&](long long x){
    339 			forn(_, 2){
    340 				int cnt = 0;
    341 				prv[n + 1] = n;
    342 				nxt[n] = n + 1;
    343 				pr[0] = 0;
    344 				int mn = 1e9;
    345 				long long cursum = 0;
    346 				forn(i, n){
    347 					if (mn < a[i]){
    348 						pr[i + 1] = cnt;
    349 						continue;
    350 					}
    351 					nxt[a[i]] = nxt[lstpr[i]];
    352 					prv[nxt[a[i]]] = a[i];
    353 					prv[a[i]] = lstpr[i];
    354 					nxt[prv[a[i]]] = a[i];
    355 					cursum += xs[a[i]].first;
    356 					++cnt;
    357 					while (cursum > x){
    358 						mn = min(mn, prv[n + 1]);
    359 						cursum -= xs[prv[n + 1]].first;
    360 						prv[n + 1] = prv[prv[n + 1]];
    361 						nxt[prv[n + 1]] = n + 1;
    362 						--cnt;
    363 					}
    364 					pr[i + 1] = cnt;
    365 				}
    366 				reverse(a.begin(), a.end());
    367 				swap(lstpr, lstsu);
    368 				swap(pr, su);
    369 			}
    370 			reverse(su.begin(), su.end());
    371 			forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
    372 			return false;
    373 		};
    374 		
    375 		long long l = 1, r = 0;
    376 		for (int x : a) r += xs[x].first;
    377 		long long res = 0;
    378 		while (l <= r){
    379 			long long m = (l + r) / 2;
    380 			if (check(m)){
    381 				res = m;
    382 				r = m - 1;
    383 			}
    384 			else{
    385 				l = m + 1;
    386 			}
    387 		}
    388 		printf("%lld\n", res);
    389 	}
    390 }
    391 ```