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 ```