codeforces-scrape

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

1454.md (6923B)


      1 Source: https://codeforces.com/blog/entry/84984
      2 
      3 [1454A - Special Permutation](/contest/1454/problem/A "Codeforces Round 686 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      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 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int n;
     28 		cin >> n;
     29 		for (int i = 0; i < n; ++i) {
     30 			cout << (i + 1) % n + 1 << " ";
     31 		}
     32 		cout << endl;
     33 	}
     34 	
     35 	return 0;
     36 }
     37 ```
     38 
     39 [1454B - Unique Bid Auction](/contest/1454/problem/B "Codeforces Round 686 (Div. 3)")
     40 
     41 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 using namespace std;
     53 
     54 int main() {
     55 #ifdef _DEBUG
     56 	freopen("input.txt", "r", stdin);
     57 //	freopen("output.txt", "w", stdout);
     58 #endif
     59 	
     60 	int t;
     61 	cin >> t;
     62 	while (t--) {
     63 		int n;
     64 		cin >> n;
     65 		vector<int> cnt(n + 1), idx(n + 1);
     66 		for (int i = 0; i < n; ++i) {
     67 			int x;
     68 			cin >> x;
     69 			++cnt[x];
     70 			idx[x] = i + 1;
     71 		}
     72 		int ans = -1;
     73 		for (int i = 0; i <= n; ++i) {
     74 			if (cnt[i] == 1) {
     75 				ans = idx[i];
     76 				break;
     77 			}
     78 		}
     79 		cout << ans << endl;
     80 	}
     81 	
     82 	return 0;
     83 }
     84 ```
     85 
     86 [1454C - Sequence Transformation](/contest/1454/problem/C "Codeforces Round 686 (Div. 3)")
     87 
     88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 
     99 using namespace std;
    100 
    101 int main() {
    102 #ifdef _DEBUG
    103 	freopen("input.txt", "r", stdin);
    104 //	freopen("output.txt", "w", stdout);
    105 #endif
    106 	
    107 	int t;
    108 	cin >> t;
    109 	while (t--) {
    110 		int n;
    111 		cin >> n;
    112 		vector<int> a(n);
    113 		for (auto &it : a) cin >> it;
    114 		vector<int> res(n + 1, 1);
    115 		n = unique(a.begin(), a.end()) - a.begin();
    116 		a.resize(n);
    117 		for (int i = 0; i < n; ++i) {
    118 			res[a[i]] += 1;
    119 		}
    120 		res[a[0]] -= 1;
    121 		res[a[n - 1]] -= 1;
    122 		int ans = 1e9;
    123 		for (int i = 0; i < n; ++i) {
    124 			ans = min(ans, res[a[i]]);
    125 		}
    126 		cout << ans << endl;
    127 	}
    128 	
    129 	return 0;
    130 }
    131 ```
    132 
    133 [1454D - Number into Sequence](/contest/1454/problem/D "Codeforces Round 686 (Div. 3)")
    134 
    135 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145 
    146 using namespace std;
    147 
    148 int main() {
    149 #ifdef _DEBUG
    150 	freopen("input.txt", "r", stdin);
    151 //	freopen("output.txt", "w", stdout);
    152 #endif
    153 	
    154 	int t;
    155 	cin >> t;
    156 	while (t--) {
    157 		long long n;
    158 		cin >> n;
    159 	
    160 		vector<pair<int, long long>> val;
    161 		for (long long i = 2; i * i <= n; ++i) {
    162 			int cnt = 0;
    163 			while (n % i == 0) {
    164 				++cnt;
    165 				n /= i;
    166 			}
    167 			if (cnt > 0) {
    168 				val.push_back({cnt, i});
    169 			}
    170 		}
    171 		if (n > 1) {
    172 			val.push_back({1, n});
    173 		}
    174 	
    175 		sort(val.rbegin(), val.rend());
    176 		vector<long long> ans(val[0].first, val[0].second);
    177 		for (int i = 1; i < int(val.size()); ++i) {
    178 			for (int j = 0; j < val[i].first; ++j) {
    179 				ans.back() *= val[i].second;
    180 			}
    181 		}
    182 	
    183 		cout << ans.size() << endl;
    184 		for (auto it : ans) cout << it << " ";
    185 		cout << endl;
    186 	}
    187 	
    188 	return 0;
    189 }
    190 ```
    191 
    192 [1454E - Number of Simple Paths](/contest/1454/problem/E "Codeforces Round 686 (Div. 3)")
    193 
    194 Idea: [vovuh](/profile/vovuh "Master vovuh")
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 
    205 using namespace std;
    206 
    207 int main() {
    208 #ifdef _DEBUG
    209 	freopen("input.txt", "r", stdin);
    210 //	freopen("output.txt", "w", stdout);
    211 #endif
    212 	
    213 	int t;
    214 	cin >> t;
    215 	while (t--) {
    216 		int n;
    217 		cin >> n;
    218 		vector<set<int>> g(n);
    219 		for (int i = 0; i < n; ++i) {
    220 			int x, y;
    221 			cin >> x >> y;
    222 			--x, --y;
    223 			g[x].insert(y);
    224 			g[y].insert(x);
    225 		}
    226 		vector<int> val(n, 1);
    227 		queue<int> leafs;
    228 		for (int i = 0; i < n; ++i) {
    229 			if (g[i].size() == 1) {
    230 				leafs.push(i);
    231 			}
    232 		}
    233 		while (!leafs.empty()) {
    234 			int v = leafs.front();
    235 			leafs.pop();
    236 			int to = *g[v].begin();
    237 			val[to] += val[v];
    238 			val[v] = 0;
    239 			g[v].clear();
    240 			g[to].erase(v);
    241 			if (g[to].size() == 1) {
    242 				leafs.push(to);
    243 			}
    244 		}
    245 		long long ans = 0;
    246 		for (int i = 0; i < n; ++i) {
    247 			ans += val[i] * 1ll * (val[i] - 1) / 2;
    248 			ans += val[i] * 1ll * (n - val[i]);
    249 		}
    250 		cout << ans << endl;
    251 	}
    252 	
    253 	return 0;
    254 }
    255 ```
    256 
    257 [1454F - Array Partition](/contest/1454/problem/F "Codeforces Round 686 (Div. 3)")
    258 
    259 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution**
    266 
    267 ```
    268 #include <bits/stdc++.h>
    269 
    270 using namespace std;
    271 
    272 bool found;
    273 
    274 void shift(multiset<int> &l, multiset<int> &r, int val) {
    275 	l.erase(l.find(val));
    276 	r.insert(val);
    277 }
    278 
    279 void check(const multiset<int> &lf, const multiset<int> &mid, const multiset<int> &rg) {
    280 	if (found || lf.empty() || mid.empty() || rg.empty()) {
    281 		return;
    282 	}
    283 	if (*lf.rbegin() == *mid.begin() && *mid.begin() == *rg.rbegin()) {
    284 		found = true;
    285 		cout << "YES" << endl;
    286 		cout << lf.size() << " " << mid.size() << " " << rg.size() << endl;
    287 	}
    288 }
    289 
    290 int main() {
    291 #ifdef _DEBUG
    292 	freopen("input.txt", "r", stdin);
    293 //	freopen("output.txt", "w", stdout);
    294 #endif
    295 	
    296 	int t;
    297 	cin >> t;
    298 	while (t--) {
    299 		int n;
    300 		cin >> n;
    301 		vector<int> a(n);
    302 		for (auto &it : a) cin >> it;
    303 		
    304 		found = false;
    305 		multiset<int> lf, mid(a.begin(), a.end()), rg;
    306 		int r = n - 1;
    307 		for (int l = 0; l < n - 2; ++l) {
    308 			shift(mid, lf, a[l]);
    309 			while (r - 1 >= l && a[r] <= *lf.rbegin()) {
    310 				shift(mid, rg, a[r]);
    311 				--r;
    312 			}
    313 			
    314 			while (r - 1 < l) {
    315 				shift(rg, mid, a[r + 1]);
    316 				++r;
    317 			}
    318 			
    319 			check(lf, mid, rg);
    320 			
    321 			shift(lf, mid, a[l]);
    322 			check(lf, mid, rg);
    323 			shift(mid, lf, a[l]);
    324 			
    325 			if (rg.empty()) continue;
    326 			
    327 			shift(rg, mid, a[r + 1]);
    328 			check(lf, mid, rg);
    329 			shift(mid, rg, a[r + 1]);
    330 		}
    331 		if (!found) {
    332 			cout << "NO" << endl;
    333 		}
    334 	}
    335 	
    336 	return 0;
    337 }
    338 ```
    339 
    340 **Solution (Gassa)**
    341 
    342 ```
    343 // Author: Ivan Kazmenko ([email protected])
    344 module solution;
    345 import std.algorithm;
    346 import std.conv;
    347 import std.range;
    348 import std.stdio;
    349 import std.string;
    350 
    351 void main ()
    352 {
    353 	auto tests = readln.strip.to !(int);
    354 	foreach (test; 0..tests)
    355 	{
    356 		auto n = readln.strip.to !(int);
    357 		auto a = readln.splitter.map !(to !(int)).array;
    358 		auto x = a.dup;
    359 		foreach (i; 1..n)
    360 		{
    361 			x[i] = max (x[i], x[i - 1]);
    362 		}
    363 		auto y = a.dup;
    364 		foreach_reverse (i; 0..n - 1)
    365 		{
    366 			y[i] = max (y[i], y[i + 1]);
    367 		}
    368 
    369 		auto v = a.maxElement;
    370 		auto maxPlaces = n.iota.filter !(i => a[i] == v).array;
    371 		int lo = maxPlaces[$ / 2];
    372 		int hi = lo + 1;
    373 
    374 		while (true)
    375 		{
    376 			if (lo == 0 || hi == n)
    377 			{
    378 				writeln ("NO");
    379 				break;
    380 			}
    381 			if (x[lo - 1] == v && y[hi] == v)
    382 			{
    383 				writeln ("YES");
    384 				writeln (lo, " ", hi - lo, " ", n - hi);
    385 				break;
    386 			}
    387 			int u = (lo - 1 == 0) ? int.min :
    388 			    min (x[lo - 2], a[lo - 1]);
    389 			int w = (hi + 1 >= n) ? int.min :
    390 			    min (y[hi + 1], a[hi]);
    391 			if (u > w)
    392 			{
    393 				v = min (v, a[lo - 1]);
    394 				lo -= 1;
    395 			}
    396 			else
    397 			{
    398 				v = min (v, a[hi]);
    399 				hi += 1;
    400 			}
    401 		}
    402 	}
    403 }
    404 ```