1714.md (8415B)
1 Source: https://codeforces.com/blog/entry/105549 2 3 [1714A - Everyone Loves to Sleep](/contest/1714/problem/A "Codeforces Round 811 (Div. 3)") 4 5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 #define int long long 17 #define pb emplace_back 18 #define mp make_pair 19 #define x first 20 #define y second 21 #define all(a) a.begin(), a.end() 22 #define rall(a) a.rbegin(), a.rend() 23 24 typedef long double ld; 25 typedef long long ll; 26 27 using namespace std; 28 29 mt19937 rnd(143); 30 31 const int inf = 1e15; 32 const int M = 1e9 + 7; 33 const ld pi = atan2(0, -1); 34 const ld eps = 1e-6; 35 36 void solve(){ 37 int n; 38 cin >> n; 39 int time, h, m; 40 cin >> h >> m; 41 time = 60 * h + m; 42 int ans = 24 * 60; 43 for(int i = 0; i < n; ++i){ 44 cin >> h >> m; 45 int t = 60 * h + m - time; 46 if(t < 0) t += 24 * 60; 47 ans = min(ans, t); 48 } 49 cout << ans / 60 << " " << ans % 60; 50 } 51 52 bool multi = true; 53 54 signed main() { 55 int t = 1; 56 if (multi)cin >> t; 57 for (; t; --t) { 58 solve(); 59 cout << endl; 60 } 61 return 0; 62 } 63 ``` 64 65 [1714B - Remove Prefix](/contest/1714/problem/B "Codeforces Round 811 (Div. 3)") 66 67 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 68 69 **Tutorial** 70 71 Tutorial is loading... 72 73 **Solution** 74 75 ``` 76 #include <bits/stdc++.h> 77 78 using namespace std; 79 80 #define forn(i, n) for (int i = 0; i < int(n); i++) 81 82 int main() { 83 int t; 84 cin >> t; 85 forn(tt, t) { 86 int n; 87 cin >> n; 88 vector<int> a(n); 89 forn(i, n) 90 cin >> a[i]; 91 bool yes = false; 92 set<int> c; 93 for (int i = n - 1; i >= 0; i--) { 94 if (c.count(a[i])) { 95 cout << i + 1 << endl; 96 yes = true; 97 break; 98 } 99 c.insert(a[i]); 100 } 101 if (!yes) 102 cout << 0 << endl; 103 } 104 } 105 ``` 106 107 [1714C - Minimum Varied Number](/contest/1714/problem/C "Codeforces Round 811 (Div. 3)") 108 109 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 110 111 **Tutorial** 112 113 Tutorial is loading... 114 115 **Solution** 116 117 ``` 118 #include <bits/stdc++.h> 119 120 using namespace std; 121 122 #define forn(i, n) for (int i = 0; i < int(n); i++) 123 124 int main() { 125 int t; 126 cin >> t; 127 forn(tt, t) { 128 int s; 129 cin >> s; 130 string result; 131 for (int d = 9; d >= 1; d--) 132 if (s >= d) { 133 result = char('0' + d) + result; 134 s -= d; 135 } 136 cout << result << endl; 137 } 138 } 139 ``` 140 141 [1714D - Color with Occurrences](/contest/1714/problem/D "Codeforces Round 811 (Div. 3)") 142 143 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include<bits/stdc++.h> 153 #define len(s) (int)s.size() 154 #define forn(i, n) for (int i = 0; i < int(n); i++) 155 156 using namespace std; 157 int ans = 0; 158 bool ok = true; 159 160 void Find(int a, int b, string &t, vector<string>&str, vector<pair<int, int>>&match){ 161 int Max = 0, id = -1, pos = -1; 162 for(int i = a; i <= b; i++){ 163 for(int j = 0; j < len(str); j++){ 164 string s = str[j]; 165 if(i + len(s) > len(t) || i + len(s) <= b) continue; 166 if(t.substr(i, len(s)) == s) { 167 if(i + len(s) > Max){ 168 Max = i + len(s); 169 id = j; 170 pos = i; 171 } 172 } 173 } 174 } 175 if(id == -1) { 176 ok = false; 177 return; 178 } 179 else{ 180 match.emplace_back(id, pos); 181 ans++; 182 if(Max == len(t)) return; 183 else Find(max(pos + 1, b +1), Max, t, str, match); 184 } 185 } 186 187 void solve(){ 188 ans = 0; 189 ok = true; 190 191 string t; 192 cin >> t; 193 int n; 194 cin >> n; 195 196 vector<string>s(n); 197 vector<pair<int, int>>match; 198 199 forn(i, n) { 200 cin >> s[i]; 201 } 202 203 Find(0, 0, t, s, match); 204 if(!ok) cout << "-1\n"; 205 else{ 206 cout << ans << endl; 207 for(auto &p : match) cout << p.first + 1 << ' ' << p.second + 1 << endl; 208 } 209 210 } 211 212 int main(){ 213 int q; 214 cin >> q; 215 while(q--){ 216 solve(); 217 } 218 return 0; 219 } 220 ``` 221 222 [1714E - Add Modulo 10](/contest/1714/problem/E "Codeforces Round 811 (Div. 3)") 223 224 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 225 226 **Tutorial** 227 228 Tutorial is loading... 229 230 **Solution** 231 232 ``` 233 #include <iostream> 234 #include <vector> 235 #include <algorithm> 236 #include <set> 237 #include <queue> 238 239 using namespace std; 240 241 int next(int x) { 242 return x + x % 10; 243 } 244 245 void solve() { 246 int n; 247 cin >> n; 248 vector<int> a(n); 249 bool flag = false; 250 for (int i = 0; i < n; ++i) { 251 cin >> a[i]; 252 if (a[i] % 5 == 0) { 253 flag = true; 254 a[i] = next(a[i]); 255 } 256 } 257 if (flag) { 258 cout << (*min_element(a.begin(), a.end()) == *max_element(a.begin(), a.end()) ? "Yes": "No") << '\n'; 259 } else { 260 bool flag2 = false, flag12 = false; 261 for (int i = 0; i < n; ++i) { 262 int x = a[i]; 263 while (x % 10 != 2) { 264 x = next(x); 265 } 266 if (x % 20 == 2) { 267 flag2 = true; 268 } else { 269 flag12 = true; 270 } 271 } 272 cout << ((flag2 & flag12) ? "No" : "Yes") << '\n'; 273 } 274 } 275 276 int main() { 277 int t = 1; 278 cin >> t; 279 for (int it = 0; it < t; ++it) { 280 solve(); 281 } 282 return 0; 283 } 284 ``` 285 286 [1714F - Build a Tree and That Is It](/contest/1714/problem/F "Codeforces Round 811 (Div. 3)") 287 288 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 289 290 **Tutorial** 291 292 Tutorial is loading... 293 294 **Solution** 295 296 ``` 297 #include <bits/stdc++.h> 298 299 using namespace std; 300 301 #define forn(i, n) for (int i = 0; i < int(n); i++) 302 303 int main() { 304 int t; 305 cin >> t; 306 forn(tt, t) { 307 int n; 308 cin >> n; 309 vector<int> d(3); 310 forn(i, 3) 311 cin >> d[i]; 312 int sum = d[0] + d[1] + d[2]; 313 if (sum % 2 == 0) { 314 vector<int> w(3); 315 forn(i, 3) 316 w[i] = sum / 2 - d[(i + 1) % 3]; 317 vector<int> sw(w.begin(), w.end()); 318 sort(sw.begin(), sw.end()); 319 if (sw[0] >= 0 && sw[1] >= 1) { 320 vector<pair<int,int>> edges; 321 int num = 3; 322 int center; 323 if (sw[0] == 0) 324 center = min_element(w.begin(), w.end()) - w.begin(); 325 else 326 center = num++; 327 forn(i, 3) { 328 int before = center; 329 forn(j, w[i] - 1) { 330 edges.push_back({before, num}); 331 before = num++; 332 } 333 if (w[i] > 0) 334 edges.push_back({before, i}); 335 } 336 if (num <= n) { 337 while (num < n) 338 edges.push_back({center, num++}); 339 cout << "YES" << endl; 340 for (auto& [u, v]: edges) 341 cout << u + 1 << " " << v + 1 << endl; 342 continue; 343 } 344 } 345 } 346 cout << "NO" << endl; 347 } 348 } 349 ``` 350 351 [1714G - Path Prefixes](/contest/1714/problem/G "Codeforces Round 811 (Div. 3)") 352 353 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 354 355 **Tutorial** 356 357 Tutorial is loading... 358 359 **Solution** 360 361 ``` 362 #pragma GCC optimize("O3","unroll-loops") 363 #pragma GCC target("avx2") 364 #include <bits/stdc++.h> 365 366 using namespace std; 367 #define int long long 368 369 const int maxn=2e5+5; 370 vector<int> ch[maxn]; 371 int a[maxn]; 372 int b[maxn]; 373 int ans[maxn]; 374 vector<int> vb; 375 int curb=0; 376 int cura=0; 377 378 void dfs(int x){ 379 curb+=b[x]; 380 cura+=a[x]; 381 vb.push_back(curb); 382 ans[x]=upper_bound(vb.begin(),vb.end(),cura)-vb.begin(); 383 for(int v:ch[x]){ 384 dfs(v); 385 } 386 curb-=b[x]; 387 cura-=a[x]; 388 vb.pop_back(); 389 } 390 int32_t main(){ 391 ios_base::sync_with_stdio(false); 392 cin.tie(0);cout.tie(0); 393 int t; 394 cin>>t; 395 while(t--){ 396 int n;cin>>n; 397 for(int i=0;i<n;++i) ch[i].clear(); 398 for(int i=1;i<n;++i){ 399 int pr,a1,b1; 400 cin>>pr>>a1>>b1; 401 --pr; 402 ch[pr].push_back(i); 403 a[i]=a1; 404 b[i]=b1; 405 } 406 dfs(0); 407 for(int i=1;i<n;++i) cout<<ans[i]-1<<' '; 408 cout<<'\n'; 409 } 410 return 0; 411 } 412 ```