codeforces-scrape

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

1257.md (9271B)


      1 Source: https://codeforces.com/blog/entry/71434
      2 
      3 [1257A - Two Rival Students](/contest/1257/problem/A "Educational Codeforces Round 76 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 import kotlin.math.abs
     15 fun main() {
     16     val q = readLine()!!.toInt()
     17     for (ct in 1..q) {
     18         val (n, x, a, b) = readLine()!!.split(' ').map { it.toInt() }
     19         println(minOf(n - 1, abs(a - b) + x))
     20     }
     21 }
     22 ```
     23 
     24 [1257B - Magic Stick](/contest/1257/problem/B "Educational Codeforces Round 76 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (Ne0n25)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36 
     37 using namespace std;
     38 
     39 void solve() {
     40 	int x, y;
     41 	cin >> x >> y;
     42 	
     43 	if (x > 3) puts("YES");
     44 	else if (x == 1) puts(y == 1 ? "YES" : "NO");
     45 	else puts(y <= 3 ? "YES" : "NO");
     46 }
     47 
     48 int main() {
     49 	int tc;
     50 	cin >> tc;
     51 	while (tc--) solve();
     52 }
     53 ```
     54 
     55 [1257C - Dominated Subarray](/contest/1257/problem/C "Educational Codeforces Round 76 (Rated for Div. 2)")
     56 
     57 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution (adedalic)**
     64 
     65 ```
     66 #include<bits/stdc++.h>
     67 using namespace std;
     68 
     69 #define sz(a) int((a).size())
     70 
     71 int n;
     72 vector<int> a;
     73 
     74 inline bool read() {
     75 	if(!(cin >> n))
     76 		return false;
     77 	a.resize(n);
     78 	for(int i = 0; i < n; i++)
     79 		cin >> a[i];
     80 	return true;
     81 }
     82 
     83 inline void solve() {
     84 	int ans = n + 5;
     85 	vector<int> lst(n + 1, -1);
     86 	for(int i = 0; i < n; i++) {
     87 		if(lst[a[i]] != -1)
     88 			ans = min(ans, i - lst[a[i]] + 1);
     89 		lst[a[i]] = i;
     90 	}
     91 	if(ans > n)
     92 		ans = -1;
     93 	cout << ans << endl;
     94 }
     95 
     96 int main() {
     97 #ifdef _DEBUG
     98 	freopen("input.txt", "r", stdin);
     99 #endif
    100 	ios_base::sync_with_stdio(false);
    101 	cin.tie(0), cout.tie(0);
    102 	cout << fixed << setprecision(15);
    103 	
    104 	int tc; cin >> tc;
    105 	while(tc--) {
    106 		assert(read());
    107 		solve();
    108 	}
    109 	return 0;
    110 }
    111 ```
    112 
    113 [1257D - Yet Another Monster Killing Problem](/contest/1257/problem/D "Educational Codeforces Round 76 (Rated for Div. 2)")
    114 
    115 Idea: [Roms](/profile/Roms "Master Roms")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution (Roms)**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 const int N = int(2e5) + 99;
    129 
    130 int t;
    131 int n;
    132 int a[N];
    133 int m;
    134 int p[N], s[N];
    135 int bst[N];
    136 
    137 int main() {	
    138 	scanf("%d", &t);
    139 	for(int tc = 0; tc < t; ++tc){
    140 		scanf("%d", &n);
    141 		for(int i = 0; i <= n; ++i) bst[i] = 0;
    142 		for(int i = 0; i < n; ++i)
    143 			scanf("%d", a + i);
    144 		scanf("%d", &m);
    145 		for(int i = 0; i < m; ++i){
    146 			scanf("%d %d", p + i, s + i);
    147 			bst[s[i]] = max(bst[s[i]], p[i]);
    148 		}
    149 		for(int i = n - 1; i >= 0; --i)
    150 			bst[i] = max(bst[i], bst[i + 1]);	
    151 		
    152 
    153 		int pos = 0;
    154 		int res = 0;
    155 		bool ok = true;
    156 		while(pos < n){
    157 			++res;
    158 			int npos = pos;
    159 			int mx = 0;
    160 			while(true){
    161 				mx = max(mx, a[npos]);
    162 				if(mx > bst[npos - pos + 1]) break;
    163 				++npos;
    164 			}
    165 	
    166 			if(pos == npos){
    167 				ok = false;
    168 				break;
    169 			}
    170 			pos = npos;
    171 		}
    172 
    173 		if(!ok) res = -1;
    174 		printf("%d\n", res);
    175 	}
    176 
    177 	return 0;
    178 }                             	            	
    179 ```
    180 
    181 [1257E - The Contest](/contest/1257/problem/E "Educational Codeforces Round 76 (Rated for Div. 2)")
    182 
    183 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Solution (BledDest)**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 
    194 using namespace std;
    195 
    196 int main() 
    197 {
    198 	int k1, k2, k3;
    199 	scanf("%d %d %d", &k1, &k2, &k3);
    200 	int n = k1 + k2 + k3;
    201 	vector<int> a(n);
    202 	for(int i = 0; i < k1; i++)
    203 	{
    204 		int x;
    205 		scanf("%d", &x);
    206 		a[x - 1] = 0;
    207 	}
    208 	for(int i = 0; i < k2; i++)
    209 	{
    210 		int x;
    211 		scanf("%d", &x);
    212 		a[x - 1] = 1;
    213 	}
    214 	for(int i = 0; i < k3; i++)
    215 	{
    216 		int x;
    217 		scanf("%d", &x);
    218 		a[x - 1] = 2;
    219 	}
    220 	
    221 	int ans = 0;
    222 	int bestp = 0;
    223 	for(int i = 0; i < n; i++)
    224 		if(a[i] != 2)
    225 			ans++;
    226 	vector<int> cntl(3);
    227 	vector<int> cntr(3);
    228 	for(int i = 0; i < n; i++)
    229 		cntr[a[i]]++;
    230 	for(int i = 0; i < n; i++)
    231 	{
    232 		cntl[a[i]]++;
    233 		cntr[a[i]]--;
    234 		bestp = max(bestp, cntl[0] - cntl[1]);
    235 		int curans = cntr[0] + cntr[1] + cntl[2] + cntl[0] - bestp;
    236 		ans = min(ans, curans);
    237 	}
    238 	
    239 	cout << ans << endl;
    240 }                    	
    241 ```
    242 
    243 [1257F - Make Them Similar](/contest/1257/problem/F "Educational Codeforces Round 76 (Rated for Div. 2)")
    244 
    245 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution (BledDest)**
    252 
    253 ```
    254 #include<bits/stdc++.h>
    255 
    256 using namespace std;
    257 
    258 typedef long long li;
    259 const int N = 143;
    260 const int K = 15;
    261 const int V = 5000000;
    262 
    263 int n;
    264 li a[N];
    265 int lst[V];
    266 map<int, int> nxt[V];
    267 int t = 1;
    268 li a1[N];
    269 li a2[N];
    270 
    271 int get_nxt(int v, int x)
    272 {
    273 	if(!nxt[v].count(x))
    274 		nxt[v][x] = t++;
    275 	return nxt[v][x];
    276 }
    277 
    278 void add(vector<int> diff, int x)
    279 {
    280 	int v = 0;
    281 	for(auto i : diff)
    282 		v = get_nxt(v, i);
    283 	lst[v] = x;
    284 }
    285 
    286 int try_find(vector<int> diff)
    287 {
    288 	int v = 0;
    289 	for(auto i : diff)
    290 	{
    291 		if(!nxt[v].count(i))
    292 			return -1;
    293 		v = nxt[v][i];
    294 	}
    295 	return lst[v];
    296 }
    297 
    298 vector<int> get_diff(li arr[N], int x)
    299 {
    300 	vector<int> cnt(n);
    301 	for(int i = 0; i < n; i++)
    302 		cnt[i] = __builtin_popcountll(arr[i] ^ x);
    303 	vector<int> diff(n - 1);
    304 	for(int i = 0; i + 1 < n; i++)
    305 		diff[i] = cnt[i + 1] - cnt[0];
    306 	return diff;
    307 }
    308 
    309 int main()
    310 {
    311 	cin >> n;
    312 	for(int i = 0; i < n; i++)
    313 		cin >> a[i];
    314 	
    315 	for(int i = 0; i < n; i++)
    316 	{
    317 		a1[i] = (a[i] >> K);
    318 		a2[i] = a[i] ^ (a1[i] << K);
    319 	}
    320 	for(int i = 0; i < (1 << K); i++)
    321 	{
    322 		vector<int> d = get_diff(a1, i);
    323 		add(d, i);
    324 	}
    325 	for(int i = 0; i < (1 << K); i++)
    326 	{
    327 		vector<int> d = get_diff(a2, i);
    328 		for(int j = 0; j + 1 < n; j++)
    329 			d[j] *= -1;
    330 		int x = try_find(d);
    331 		if(x != -1)
    332 		{
    333 			li res = (li(x) << K) ^ i;
    334 			cout << res << endl;
    335 			return 0;
    336 		}
    337 	}
    338 	cout << -1 << endl;
    339 	return 0;
    340 	return 0;
    341 }
    342 ```
    343 
    344 [1257G - Divisor Set](/contest/1257/problem/G "Educational Codeforces Round 76 (Rated for Div. 2)")
    345 
    346 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    347 
    348 **Tutorial**
    349 
    350 Tutorial is loading...
    351 
    352 **Solution (adedalic)**
    353 
    354 ```
    355 #include<bits/stdc++.h>
    356 
    357 using namespace std;
    358 
    359 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    360 #define sz(a) int((a).size())
    361 
    362 const int LOGN = 18;
    363 const int MOD = 998244353;
    364 int g = 3;
    365 
    366 int mul(int a, int b) {
    367 	return int(a * 1ll * b % MOD);
    368 }
    369 int norm(int a) {
    370 	while(a >= MOD) a -= MOD;
    371 	while(a < 0) a += MOD;
    372 	return a;
    373 }
    374 int binPow (int a, int k) {
    375 	int ans = 1;
    376 	for (; k > 0; k >>= 1) {
    377 		if (k & 1)
    378 			ans = mul(ans, a);
    379 		a = mul(a, a);
    380 	}
    381 	return ans;
    382 }
    383 int inv(int a) {
    384 	return binPow(a, MOD - 2);
    385 }
    386 
    387 vector<int> w[LOGN], rv;
    388 bool precalced = false;
    389 
    390 void precalc() {
    391 	if(precalced)
    392 		return;
    393 	precalced = true;
    394 	
    395     int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    396     fore(st, 0, LOGN) {
    397         w[st].assign(1 << st, 1);
    398 
    399         int bw = binPow(wb, 1 << (LOGN - st - 1));
    400         int cw = 1;
    401 
    402         fore(k, 0, (1 << st)) {
    403             w[st][k] = cw;
    404             cw = mul(cw, bw);
    405         }
    406     }
    407     
    408     rv.assign(1 << LOGN, 0);
    409     fore(i, 1, sz(rv))
    410 		rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
    411 }
    412 
    413 const int MX = (1 << LOGN) + 3;
    414 
    415 inline void fft(int a[MX], int n, bool inverse) {
    416 	precalc();
    417 	
    418     int ln = __builtin_ctz(n);
    419     assert((1 << ln) < MX);
    420     assert((1 << ln) == n);
    421 
    422     fore(i, 0, n) {
    423         int ni = rv[i] >> (LOGN - ln);
    424         if(i < ni) swap(a[i], a[ni]);
    425     }
    426 
    427     for(int st = 0; (1 << st) < n; st++) {
    428         int len = (1 << st);
    429         for(int k = 0; k < n; k += (len << 1)) {
    430         	fore(pos, k, k + len) {
    431                 int l = a[pos];
    432                 int r = mul(a[pos + len], w[st][pos - k]);
    433 
    434                 a[pos] = norm(l + r);
    435                 a[pos + len] = norm(l - r);
    436             }
    437         }
    438     }
    439     
    440     if(inverse) {
    441         int in = inv(n);
    442         fore(i, 0, n)
    443             a[i] = mul(a[i], in);
    444         reverse(a + 1, a + n);
    445     }
    446 }
    447 
    448 int aa[MX], bb[MX], cc[MX];
    449 
    450 vector<int> multiply(const vector<int> &a, const vector<int> &b) {
    451 	int ln = 1;
    452 	while(ln < (sz(a) + sz(b)))
    453 		ln <<= 1;
    454 	
    455 	fore(i, 0, ln)
    456 		aa[i] = (i < sz(a) ? a[i] : 0);
    457 	fore(i, 0, ln)
    458 		bb[i] = (i < sz(b) ? b[i] : 0);
    459 		
    460 	fft(aa, ln, false);
    461 	fft(bb, ln, false);
    462 	
    463 	fore(i, 0, ln)
    464 		cc[i] = mul(aa[i], bb[i]);
    465 	fft(cc, ln, true);
    466 	
    467 	vector<int> ans(cc, cc + ln);
    468 	while(ans.back() == 0)
    469 		ans.pop_back();
    470 	return ans;
    471 }
    472 
    473 int n;
    474 vector<int> ps;
    475 
    476 inline bool read() {
    477 	if(!(cin >> n))
    478 		return false;
    479 	ps.resize(n);
    480 	fore(i, 0, n)
    481 		cin >> ps[i];
    482 	return true;
    483 }
    484 
    485 struct cmp {
    486 	bool operator ()(const vector<int> &a, const vector<int> &b) {
    487 		return sz(a) < sz(b);
    488 	}
    489 };
    490 
    491 inline void solve() {
    492 	map<int, int> cnt;
    493 	fore (i, 0, n)
    494 		cnt[ps[i]]++;
    495 	
    496 	multiset< vector<int>, cmp > polys;
    497 	for (auto p : cnt)
    498 		polys.emplace(p.second + 1, 1);
    499 	
    500 	while (sz(polys) > 1) {
    501 		auto it2 = polys.begin();
    502 		auto it1 = it2++;
    503 		polys.insert(multiply(*it1, *it2));
    504 		
    505 		polys.erase(it1);
    506 		polys.erase(it2);
    507 	}
    508 
    509 	auto poly = *polys.begin();
    510 //	cerr << '[';
    511 //	fore(i, 0, sz(poly)) {
    512 //		if(i) cerr << ", ";
    513 //		cerr << poly[i];
    514 //	}
    515 //	cerr << ']' << endl;
    516 
    517 	cout << poly[n / 2] << endl;
    518 }
    519 
    520 int main() {
    521 #ifdef _DEBUG
    522 	freopen("input.txt", "r", stdin);
    523 	int tt = clock();
    524 #endif
    525 	ios_base::sync_with_stdio(false);
    526 	cin.tie(0), cout.tie(0);
    527 	cout << fixed << setprecision(15);
    528 	
    529 	if(read()) {
    530 		solve();
    531 		
    532 #ifdef _DEBUG
    533 		cerr << "TIME = " << clock() - tt << endl;
    534 		tt = clock();
    535 #endif
    536 	}
    537 	return 0;
    538 }
    539 ```