1512.md (8237B)
1 Source: https://codeforces.com/blog/entry/89535 2 3 [1512A - Spy Detected!](/contest/1512/problem/A "Codeforces Round 713 (Div. 3)") 4 5 Author: [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 typedef long long ll; 19 20 void solve() { 21 int n; 22 cin >> n; 23 vector<int> v(n); 24 for (int &e : v) { 25 cin >> e; 26 } 27 vector<int> a = v; 28 sort(a.begin(), a.end()); 29 for (int i = 0; i < n; i++) { 30 if (v[i] != a[1]) { 31 cout << i + 1 << "\n"; 32 } 33 } 34 } 35 36 int main() { 37 int n; 38 cin >> n; 39 while (n--) { 40 solve(); 41 } 42 return 0; 43 } 44 ``` 45 46 [1512B - Almost Rectangle](/contest/1512/problem/B "Codeforces Round 713 (Div. 3)") 47 48 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 #define forn(i, n) for (int i = 0; i < int(n); i++) 62 63 int main() { 64 int t; 65 cin >> t; 66 forn(tt, t) { 67 int n; 68 cin >> n; 69 vector<string> f(n); 70 vector<pair<int,int>> p; 71 forn(i, n) { 72 cin >> f[i]; 73 forn(j, n) 74 if (f[i][j] == '*') 75 p.push_back({i, j}); 76 } 77 78 p.push_back(p[0]); 79 p.push_back(p[1]); 80 if (p[0].first == p[1].first) { 81 p[2].first = (p[2].first + 1) % n; 82 p[3].first = (p[3].first + 1) % n; 83 } else if (p[0].second == p[1].second) { 84 p[2].second = (p[2].second + 1) % n; 85 p[3].second = (p[3].second + 1) % n; 86 } else 87 swap(p[2].first, p[3].first); 88 89 f[p[2].first][p[2].second] = '*'; 90 f[p[3].first][p[3].second] = '*'; 91 forn(i, n) 92 cout << f[i] << endl; 93 } 94 } 95 ``` 96 97 [1512C - A-B Palindrome](/contest/1512/problem/C "Codeforces Round 713 (Div. 3)") 98 99 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution** 106 107 ``` 108 #include <bits/stdc++.h> 109 using namespace std; 110 111 void no() { 112 cout << "-1" << endl; 113 } 114 115 void solve() { 116 int a, b; 117 cin >> a >> b; 118 string s; 119 cin >> s; 120 for (int times = 0; times < 2; times++) { 121 for (int i = 0; i < (int) s.size(); i++) { 122 int j = (int) s.size() - i - 1; 123 if (s[i] != '?') { 124 if (s[j] == '?') { 125 s[j] = s[i]; 126 } else if (s[i] != s[j]) { 127 no(); 128 return; 129 } 130 } 131 } 132 reverse(s.begin(), s.end()); 133 } 134 a -= count(s.begin(), s.end(), '0'); 135 b -= count(s.begin(), s.end(), '1'); 136 int ques = count(s.begin(), s.end(), '?'); 137 bool emptyMid = (s.size() % 2 == 1 && s[s.size() / 2] == '?'); 138 if (a < 0 || b < 0 || a + b != ques || (emptyMid && a % 2 == 0 && b % 2 == 0)) { 139 no(); 140 return; 141 } 142 if (a % 2 == 1 || b % 2 == 1) { 143 int i = s.size() / 2; 144 if (s[i] != '?') { 145 no(); 146 return; 147 } 148 s[i] = (a % 2 == 1 ? '0' : '1'); 149 if (a % 2 == 1) { 150 a--; 151 } else { 152 b--; 153 } 154 } 155 if (a % 2 == 1 || b % 2 == 1) { 156 no(); 157 return; 158 } 159 for (int i = 0; i < (int) s.size(); i++) { 160 if (s[i] == '?') { 161 int j = s.size() - i - 1; 162 if (a > 0) { 163 a -= 2; 164 s[i] = s[j] = '0'; 165 } else { 166 b -= 2; 167 s[i] = s[j] = '1'; 168 } 169 } 170 } 171 cout << s << endl; 172 } 173 174 int main() { 175 int tests; 176 cin >> tests; 177 while (tests-- > 0) { 178 solve(); 179 } 180 return 0; 181 } 182 ``` 183 184 [1512D - Corrupted Array](/contest/1512/problem/D "Codeforces Round 713 (Div. 3)") 185 186 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 **Solution** 193 194 ``` 195 #include <bits/stdc++.h> 196 using namespace std; 197 198 void no() { 199 cout << "-1" << endl; 200 } 201 202 void solve() { 203 int n; 204 cin >> n; 205 vector<int> b(n + 2); 206 for (int &x : b) { 207 cin >> x; 208 } 209 210 multiset<int> have(b.begin(), b.end()); 211 long long sum = accumulate(b.begin(), b.end(), 0LL); 212 for (int x : b) { 213 have.erase(have.find(x)); 214 sum -= x; 215 if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end()) { 216 have.erase(have.find(sum / 2)); 217 for (int y : have) { 218 cout << y << " "; 219 } 220 cout << endl; 221 return; 222 } 223 sum += x; 224 have.insert(x); 225 } 226 no(); 227 } 228 229 int main() { 230 int tests; 231 cin >> tests; 232 while (tests-- > 0) { 233 solve(); 234 } 235 return 0; 236 } 237 ``` 238 239 [1512E - Permutation by Sum](/contest/1512/problem/E "Codeforces Round 713 (Div. 3)") 240 241 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 242 243 **Tutorial** 244 245 Tutorial is loading... 246 247 **Solution** 248 249 ``` 250 #include <bits/stdc++.h> 251 252 using namespace std; 253 using ll = long long; 254 255 void solve() { 256 int n, l, r, s; 257 cin >> n >> l >> r >> s; 258 l--; r--; 259 for (int first = 1; first + (r - l) <= n; first++) { 260 int sum = 0; 261 for (int i = l; i <= r; i++) { 262 sum += first + (i - l); 263 } 264 if (sum <= s && s - sum <= r - l + 1) { 265 int needAdd = r - (s - sum) + 1; 266 vector<int> ans(n); 267 set<int> non_blocked; 268 for (int i = 1; i <= n; i++) { 269 non_blocked.insert(i); 270 } 271 for (int i = l; i <= r; i++) { 272 ans[i] = first + (i - l); 273 if (i >= needAdd) { 274 ans[i]++; 275 } 276 non_blocked.erase(ans[i]); 277 } 278 if (ans[r] > n) { 279 continue; 280 } 281 non_blocked.erase(ans[r]); 282 for (int i = 0; i < l; i++) { 283 ans[i] = *non_blocked.begin(); 284 non_blocked.erase(non_blocked.begin()); 285 } 286 for (int i = r + 1; i < n; i++) { 287 ans[i] = *non_blocked.begin(); 288 non_blocked.erase(non_blocked.begin()); 289 } 290 for (int i : ans) { 291 cout << i << " "; 292 } 293 cout << "\n"; 294 return; 295 } 296 } 297 cout << "-1\n"; 298 } 299 300 int main() { 301 ios_base::sync_with_stdio(false); 302 cin.tie(nullptr); cout.tie(nullptr); 303 int n; 304 cin >> n; 305 while (n--) { 306 solve(); 307 } 308 } 309 ``` 310 311 [1512F - Education](/contest/1512/problem/F "Codeforces Round 713 (Div. 3)") 312 313 Author: [sodafago](/profile/sodafago "Specialist sodafago") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution** 320 321 ``` 322 #include <bits/stdc++.h> 323 324 using namespace std; 325 326 typedef long long ll; 327 328 void solve() { 329 int n, c; 330 cin >> n >> c; 331 vector<int> a(n); 332 vector<int> b(n - 1); 333 for (int &e : a) { 334 cin >> e; 335 } 336 for (int &e : b) { 337 cin >> e; 338 } 339 b.push_back(0); 340 ll ans = 1e18; 341 ll cur = 0; 342 ll bal = 0; 343 for (int i = 0; i < n; i++) { 344 ans = min(ans, cur + max(0ll, c - bal + a[i] - 1) / a[i]); 345 ll newDays = max(0ll, b[i] - bal + a[i] - 1) / a[i]; 346 cur += newDays + 1; 347 bal += a[i] * newDays - b[i]; 348 } 349 cout << ans << "\n"; 350 } 351 352 int main() { 353 int n; 354 cin >> n; 355 while (n--) { 356 solve(); 357 } 358 return 0; 359 } 360 ``` 361 362 [1512G - Short Task](/contest/1512/problem/G "Codeforces Round 713 (Div. 3)") 363 364 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 365 366 **Tutorial** 367 368 Tutorial is loading... 369 370 **Solution** 371 372 ``` 373 #include <bits/stdc++.h> 374 using namespace std; 375 376 const int N = (int) 1e7 + 100; 377 378 long long s[N]; 379 int d[N]; 380 int ans[N]; 381 382 int main() { 383 fill(d, d + N, -1); 384 d[1] = 1; 385 for (int i = 2; i * i < N; i++) { 386 if (d[i] == -1) { 387 d[i] = i; 388 for (int j = i * i; j < N; j += i) { 389 if (d[j] == -1) { 390 d[j] = i; 391 } 392 } 393 } 394 } 395 s[1] = 1; 396 for (int i = 2; i < N; i++) { 397 if (d[i] == -1) { 398 d[i] = i; 399 s[i] = i + 1; 400 } else { 401 int j = i; 402 s[i] = 1; 403 while (j % d[i] == 0) { 404 j /= d[i]; 405 s[i] = s[i] * d[i] + 1; 406 } 407 s[i] *= s[j]; 408 } 409 } 410 fill(ans, ans + N, -1); 411 for (int i = N - 1; i > 0; i--) { 412 if (s[i] < N) { 413 ans[s[i]] = i; 414 } 415 } 416 int tests; 417 cin >> tests; 418 while (tests-- > 0) { 419 int c; 420 cin >> c; 421 cout << ans[c] << endl; 422 } 423 return 0; 424 } 425 ```