1263.md (7998B)
1 Source: https://codeforces.com/blog/entry/71844 2 3 [1263A - Sweet Problem](/contest/1263/problem/A "Codeforces Round 603 (Div. 2)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (MikeMirzayanov)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 20 int main() { 21 int t; 22 cin >> t; 23 forn(tt, t) { 24 int a[3]; 25 cin >> a[0] >> a[1] >> a[2]; 26 sort(a, a + 3); 27 if (a[2] <= a[0] + a[1]) 28 cout << (a[0] + a[1] + a[2]) / 2 << endl; 29 else 30 cout << a[0] + a[1] << endl; 31 } 32 } 33 ``` 34 35 [1263B - PIN Codes](/contest/1263/problem/B "Codeforces Round 603 (Div. 2)") 36 37 Idea: [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (Stepavly)** 44 45 ``` 46 #include <bits/stdc++.h> 47 using namespace std; 48 49 void solve() { 50 int n; 51 cin >> n; 52 53 vector<char> calced(n); 54 vector<string> a(n); 55 set<string> have; 56 int res = 0; 57 58 for (string &pin : a) { 59 cin >> pin; 60 have.insert(pin); 61 } 62 63 for (int i = 0; i < n; i++) { 64 if (calced[i]) { 65 continue; 66 } 67 68 vector<int> sameIds; 69 70 for (int j = i + 1; j < n; j++) { 71 if (a[i] == a[j]) { 72 sameIds.push_back(j); 73 calced[j] = 1; 74 res++; 75 76 for (int k = 0; k < 4 && a[i] == a[j]; k++) { 77 for (char c = '0'; c <= '9'; c++) { 78 string t = a[j]; 79 t[k] = c; 80 81 if (!have.count(t)) { 82 have.insert(t); 83 a[j] = t; 84 break; 85 } 86 } 87 } 88 } 89 } 90 } 91 92 cout << res << "\n"; 93 94 for (string& s : a) { 95 cout << s << "\n"; 96 } 97 } 98 99 int main() { 100 int test; 101 cin >> test; 102 103 while (test--) { 104 solve(); 105 } 106 } 107 ``` 108 109 [1263C - Everyone is a Winner!](/contest/1263/problem/C "Codeforces Round 603 (Div. 2)") 110 111 Idea: [unreal.eugene](/profile/unreal.eugene "Candidate Master unreal.eugene") 112 113 **Tutorial** 114 115 Tutorial is loading... 116 117 **Solution (unreal.eugene)** 118 119 ``` 120 // #pragma GCC optimize("Ofast") 121 // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 122 123 #include <bits/stdc++.h> 124 #define ALL(s) (s).begin(), (s).end() 125 #define rALL(s) (s).rbegin(), (s).rend() 126 #define sz(s) (int)(s).size() 127 #define mkp make_pair 128 #define pb push_back 129 #define sqr(s) ((s) * (s)) 130 131 using namespace std; 132 133 typedef long long ll; 134 typedef long double ld; 135 typedef unsigned long long ull; 136 typedef unsigned int ui; 137 138 #ifdef EUGENE 139 mt19937 rng(1337); 140 #else 141 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 142 #endif 143 144 void solve() { 145 int n; 146 cin >> n; 147 vector<int> ans; 148 int s = (int)sqrtl(n); 149 for (int i = 0; i <= s; i++) 150 ans.pb(i); 151 for (int i = 1; i <= s; i++) 152 ans.pb(n / i); 153 sort(ALL(ans)); 154 ans.resize(unique(ALL(ans)) - ans.begin()); 155 cout << sz(ans) << endl; 156 for (int &x : ans) 157 cout << x << " "; 158 cout << endl; 159 } 160 161 int main() { 162 ios::sync_with_stdio(false); cin.tie(0); 163 #ifdef EUGENE 164 freopen("input.txt", "r", stdin); 165 // freopen("output.txt", "r", stdout); 166 #endif 167 168 int t; 169 cin >> t; 170 while (t--) 171 solve(); 172 } 173 ``` 174 175 [1263D - Secret Passwords](/contest/1263/problem/D "Codeforces Round 603 (Div. 2)") 176 177 Idea: [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 178 179 **Tutorial** 180 181 Tutorial is loading... 182 183 **Solution (Stepavly)** 184 185 ``` 186 #include <bits/stdc++.h> 187 using namespace std; 188 189 const int N = (int)2e5 + 100; 190 191 vector<int> g[N]; 192 char used[N]; 193 194 void addEdge(int v, int u) { 195 g[v].push_back(u); 196 g[u].push_back(v); 197 } 198 199 void dfs(int v) { 200 used[v] = 1; 201 202 for (int to : g[v]) { 203 if (!used[to]) { 204 dfs(to); 205 } 206 } 207 } 208 209 int main() { 210 int n; 211 cin >> n; 212 213 for (int i = 0; i < n; i++) { 214 string s; 215 cin >> s; 216 217 for (char c : s) { 218 addEdge(i, n + c - 'a'); 219 } 220 } 221 222 int res = 0; 223 224 for (int i = n; i < n + 26; i++) { 225 if (!g[i].empty() && !used[i]) { 226 dfs(i); 227 res++; 228 } 229 } 230 231 cout << res; 232 233 return 0; 234 } 235 ``` 236 237 [1263E - Editor](/contest/1263/problem/E "Codeforces Round 603 (Div. 2)") 238 239 Idea: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 240 241 **Tutorial** 242 243 Tutorial is loading... 244 245 **Solution (Supermagzzz)** 246 247 ``` 248 #include <bits/stdc++.h> 249 250 using namespace std; 251 252 using ll = long long; 253 using ld = long double; 254 255 struct MyStack { 256 int cnt = 0; 257 int allOpens = 0; 258 stack<int> s; 259 stack<int> minValue; 260 stack<int> maxValue; 261 262 void push(int x) { 263 s.push(x); 264 cnt += x; 265 if (x == 1) { 266 allOpens += 1; 267 } 268 minValue.push((minValue.size() ? min(minValue.top(), cnt) : cnt)); 269 maxValue.push((maxValue.size() ? max(maxValue.top(), cnt) : cnt)); 270 } 271 272 void pop() { 273 if (s.size() == 0) { 274 return; 275 } 276 cnt -= s.top(); 277 if (s.top() == 1) { 278 allOpens -= 1; 279 } 280 s.pop(); 281 minValue.pop(); 282 maxValue.pop(); 283 } 284 285 int top() { 286 return s.top(); 287 } 288 289 bool isCorrect() { 290 return (minValue.size() == 0 || minValue.top() >= 0); 291 } 292 293 int depth() { 294 return (maxValue.size() ? maxValue.top() : 0); 295 } 296 }; 297 298 int main() { 299 int n; 300 cin >> n; 301 string s; 302 cin >> s; 303 MyStack left, right; 304 vector<int> ans(n); 305 for (int i = 0; i < n; i++) { 306 right.push(0); 307 } 308 left.push(0); 309 int pos = 0; 310 for (int i = 0; i < n; i++) { 311 if (s[i] == 'L') { 312 if (pos != 0) { 313 pos--; 314 right.push(-left.top()); 315 left.pop(); 316 } 317 } else if (s[i] == 'R') { 318 pos++; 319 left.push(-right.top()); 320 right.pop(); 321 } else if (s[i] == '(') { 322 left.pop(); 323 left.push(1); 324 } else if (s[i] == ')') { 325 left.pop(); 326 left.push(-1); 327 } else { 328 left.pop(); 329 left.push(0); 330 } 331 if (left.isCorrect() && right.isCorrect() && left.cnt == right.cnt) { 332 cout << max({left.depth(), right.depth(), left.cnt}) << " "; 333 } else { 334 cout << "-1 "; 335 } 336 } 337 } 338 ``` 339 340 [1263F - Economic Difficulties](/contest/1263/problem/F "Codeforces Round 603 (Div. 2)") 341 342 Idea: [AdvancerMan](/profile/AdvancerMan "Candidate Master AdvancerMan") 343 344 **Tutorial** 345 346 Tutorial is loading... 347 348 **Solution (Rox)** 349 350 ``` 351 #include <bits/stdc++.h> 352 353 using namespace std; 354 355 using ll = long long; 356 using ld = long double; 357 358 #define sz(x) int((x).size()) 359 #define all(x) begin(x), end(x) 360 361 #ifdef LOCAL 362 #define eprint(x) cerr << #x << " = " << (x) << endl 363 #define eprintf(args...) fprintf(stderr, args), fflush(stderr) 364 #else 365 #define eprint(x) 366 #define eprintf(...) 367 #endif 368 369 vector<vector<int>> precalc(int n, vector<int> p, vector<int> id) { 370 vector<vector<int>> res(n, vector<int>(n)); 371 372 for (int l = 0; l < n; l++) { 373 vector<int> deg(sz(p)); 374 for (int i = 1; i < sz(p); i++) 375 deg[p[i]]++; 376 377 int val = 0; 378 for (int r = l; r < n; r++) { 379 int v = id[r]; 380 while (v != 0 && deg[v] == 0) { 381 deg[p[v]]--; 382 v = p[v]; 383 val++; 384 } 385 res[l][r] = val; 386 } 387 } 388 389 return res; 390 } 391 392 int main() { 393 ios::sync_with_stdio(false); 394 cin.tie(nullptr); 395 396 int n; 397 cin >> n; 398 399 vector<vector<int>> p(2); 400 vector<vector<int>> id(2); 401 for (int i = 0; i < 2; i++) { 402 int vn; 403 cin >> vn; 404 p[i].resize(vn); 405 for (int v = 1; v < vn; v++) { 406 cin >> p[i][v]; 407 p[i][v]--; 408 } 409 id[i].resize(n); 410 for (int j = 0; j < n; j++) { 411 cin >> id[i][j]; 412 id[i][j]--; 413 } 414 } 415 416 vector<vector<vector<int>>> cost(2); 417 for (int i = 0; i < 2; i++) 418 cost[i] = precalc(n, p[i], id[i]); 419 420 vector<int> dp(n + 1); 421 for (int i = 0; i < n; i++) { 422 for (int j = i + 1; j <= n; j++) { 423 dp[j] = max(dp[j], dp[i] + max( 424 cost[0][i][j - 1], 425 cost[1][i][j - 1] 426 )); 427 } 428 } 429 430 cout << dp[n] << endl; 431 } 432 ```