codeforces-scrape

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

1472.md (7087B)


      1 Source: https://codeforces.com/blog/entry/86406
      2 
      3 All problems were invented [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and developed by me [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") and [Stepavly](/profile/Stepavly "Master Stepavly").
      4 
      5 [1472A - Cards for Friends](/contest/1472/problem/A "Codeforces Round 693 (Div. 3)")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 using ll = long long;
     18 
     19 void solve() {
     20   int w, h, n;
     21   cin >> w >> h >> n;
     22   int res = 1;
     23   while (w % 2 == 0) {
     24     w /= 2;
     25     res *= 2;
     26   }
     27   while (h % 2 == 0) {
     28     h /= 2;
     29     res *= 2;
     30   }
     31   cout << (res >= n ? "YES\n" : "NO\n");
     32 }
     33 
     34 int main() {
     35   int t;
     36   cin >> t;
     37   while (t--) {
     38     solve();
     39   }
     40 }
     41 ```
     42 
     43 [1472B - Fair Division](/contest/1472/problem/B "Codeforces Round 693 (Div. 3)")
     44 
     45 **Editorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 
     54 using namespace std;
     55 using ll = long long;
     56 
     57 void solve() {
     58   int n;
     59   cin >> n;
     60   int cnt1 = 0, cnt2 = 0;
     61   for (int i = 0; i < n; i++) {
     62     int c;
     63     cin >> c;
     64     if (c == 1) {
     65       cnt1++;
     66     } else {
     67       cnt2++;
     68     }
     69   }
     70   if ((cnt1 + 2 * cnt2) % 2 != 0) {
     71     cout << "NO\n";
     72   } else {
     73     int sum = (cnt1 + 2 * cnt2) / 2;
     74     if (sum % 2 == 0 || (sum % 2 == 1 && cnt1 != 0)) {
     75       cout << "YES\n";
     76     } else {
     77       cout << "NO\n";
     78     }
     79   }
     80 }
     81 
     82 int main() {
     83   int t;
     84   cin >> t;
     85   while (t--) {
     86     solve();
     87   }
     88 }
     89 ```
     90 
     91 [1472C - Long Jumps](/contest/1472/problem/C "Codeforces Round 693 (Div. 3)")
     92 
     93 **Editorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 using namespace std;
    102 
    103 void solve() {
    104   int n;
    105   cin >> n;
    106   vector<int> a(n);
    107   for (int &x : a) {
    108     cin >> x;
    109   }
    110 
    111   vector<int> dp(n);
    112   for (int i = n - 1; i >= 0; i--) {
    113     dp[i] = a[i];
    114     int j = i + a[i];
    115     if (j < n) {
    116       dp[i] += dp[j];
    117     }
    118   }
    119   cout << *max_element(dp.begin(), dp.end()) << endl;
    120 }
    121 
    122 int main() {
    123   int tests;
    124   cin >> tests;
    125   while (tests-- > 0) {
    126     solve();
    127   }
    128   return 0;
    129 }
    130 ```
    131 
    132 [1472D - Even-Odd Game](/contest/1472/problem/D "Codeforces Round 693 (Div. 3)")
    133 
    134 **Editorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution**
    139 
    140 ```
    141 #include <bits/stdc++.h>
    142 
    143 using namespace std;
    144 using ll = long long;
    145 
    146 void solve() {
    147   int n;
    148   cin >> n;
    149   vector<int> v(n);
    150   for (int &e : v) {
    151     cin >> e;
    152   }
    153   sort(v.rbegin(), v.rend());
    154   ll ans = 0;
    155   for (int i = 0; i < n; i++) {
    156     if (i % 2 == 0) {
    157       if (v[i] % 2 == 0) {
    158         ans += v[i];
    159       }
    160     } else {
    161       if (v[i] % 2 == 1) {
    162         ans -= v[i];
    163       }
    164     }
    165   }
    166   if (ans == 0) {
    167     cout << "Tie\n";
    168   } else if (ans > 0) {
    169     cout << "Alice\n";
    170   } else {
    171     cout << "Bob\n";
    172   }
    173 }
    174 
    175 int main() {
    176   int t;
    177   cin >> t;
    178   while (t--) {
    179     solve();
    180   }
    181   return 0;
    182 }
    183 ```
    184 
    185 [1472E - Correct Placement](/contest/1472/problem/E "Codeforces Round 693 (Div. 3)")
    186 
    187 **Editorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Solution**
    192 
    193 ```
    194 #include <bits/stdc++.h>
    195 using namespace std;
    196 
    197 using pii = pair<int, int>;
    198 
    199 struct man {
    200   int h, w, id;
    201 };
    202 
    203 bool operator<(const man &a, const man &b) {
    204   return tie(a.h, a.w, a.id) < tie(b.h, b.w, b.id);
    205 }
    206 
    207 struct my_min {
    208   pii mn1, mn2;
    209 };
    210 
    211 vector<pair<int, my_min>> createPrefMins(const vector<man>& a) {
    212   vector<pair<int, my_min>> prefMin;
    213   my_min curMin{pii(INT_MAX, -1), pii(INT_MAX, -1)};
    214   for (auto x : a) {
    215     if (x.w < curMin.mn1.first) {
    216       curMin.mn2 = curMin.mn1;
    217       curMin.mn1 = pii(x.w, x.id);
    218     } else {
    219       curMin.mn2 = min(curMin.mn2, pii(x.w, x.id));
    220     }
    221     prefMin.emplace_back(x.h, curMin);
    222   }
    223   return prefMin;
    224 }
    225 
    226 int findAny(const vector<pair<int, my_min>> &mins, int h, int w, int id) {
    227   int l = -1, r = (int) mins.size();
    228   while (r - l > 1) {
    229     int m = (l + r) / 2;
    230     if (mins[m].first < h) {
    231       l = m;
    232     } else {
    233       r = m;
    234     }
    235   }
    236   if (l == -1) {
    237     return -1;
    238   }
    239 
    240   auto mn1 = mins[l].second.mn1;
    241   auto mn2 = mins[l].second.mn2;
    242   if (mn1.second != id) {
    243     return mn1.first < w ? mn1.second + 1 : -1;
    244   }
    245   return mn2.first < w ? mn2.second + 1 : -1;
    246 }
    247 
    248 void solve() {
    249   int n;
    250   cin >> n;
    251   vector<man> hor, ver;
    252   vector<pii> a;
    253   for (int i = 0; i < n; i++) {
    254     int h, w;
    255     cin >> h >> w;
    256     hor.push_back({h, w, i});
    257     ver.push_back({w, h, i});
    258     a.emplace_back(h, w);
    259   }
    260 
    261   sort(hor.begin(), hor.end());
    262   sort(ver.begin(), ver.end());
    263 
    264   auto horMins = createPrefMins(hor);
    265   auto verMins = createPrefMins(ver);
    266 
    267   for (int i = 0; i < n; i++) {
    268     auto[h, w] = a[i];
    269     int id = findAny(horMins, h, w, i);
    270     if (id == -1) {
    271       id = findAny(verMins, h, w, i);
    272     }
    273     cout << id << " ";
    274   }
    275   cout << endl;
    276 }
    277 
    278 int main() {
    279   int tests;
    280   cin >> tests;
    281   while (tests-- > 0) {
    282     solve();
    283   }
    284   return 0;
    285 }
    286 ```
    287 
    288 [1472F - New Year's Puzzle](/contest/1472/problem/F "Codeforces Round 693 (Div. 3)")
    289 
    290 **Editorial**
    291 
    292 Tutorial is loading...
    293 
    294 **Solution**
    295 
    296 ```
    297 #include <bits/stdc++.h>
    298 
    299 using namespace std;
    300 using ll = long long;
    301 
    302 void solve() {
    303   int n, m;
    304   cin >> n >> m;
    305   map<int, int> v;
    306   for (int i = 0; i < m; i++) {
    307     int x, y;
    308     cin >> x >> y;
    309     v[y] |= (1 << (x - 1));
    310   }
    311   const int FULL = 3;
    312   v[2e9] = FULL;
    313   int hasLast = 0, lastColor = 0;
    314   for (auto[x, mask] : v) {
    315     if (mask != FULL && hasLast) {
    316       int color = (x + mask) % 2;
    317       if (lastColor == color) {
    318         cout << "NO\n";
    319         return;
    320       } else {
    321         hasLast = false;
    322       }
    323     } else if (mask == FULL && hasLast) {
    324         cout << "NO\n";
    325         return;
    326     } else if (mask != FULL) {
    327       lastColor = (x + mask) % 2;
    328       hasLast = true;
    329     }
    330   }
    331   cout << "YES\n";
    332 }
    333 
    334 int main() {
    335   int t;
    336   cin >> t;
    337   while (t--) {
    338     solve();
    339   }
    340   return 0;
    341 }
    342 ```
    343 
    344 [1472G - Moving to the Capital](/contest/1472/problem/G "Codeforces Round 693 (Div. 3)")
    345 
    346 **Editorial**
    347 
    348 Tutorial is loading...
    349 
    350 **Solution**
    351 
    352 ```
    353 #include <bits/stdc++.h>
    354 using namespace std;
    355 
    356 vector<int> calcDist(vector<vector<int>> const &g) {
    357   vector<int> dist(g.size(), -1);
    358   dist[1] = 0;
    359   queue<int> pq;
    360   pq.push(1);
    361   while (!pq.empty()) {
    362     int u = pq.front();
    363     pq.pop();
    364     for (int v : g[u]) {
    365       if (dist[v] == -1) {
    366         dist[v] = dist[u] + 1;
    367         pq.push(v);
    368       }
    369     }
    370   }
    371 
    372   return dist;
    373 }
    374 
    375 void dfs(int u, vector<vector<int>> const &g, vector<int> const &dist, vector<int> &dp, vector<bool> &used) {
    376   used[u] = true;
    377   dp[u] = dist[u];
    378   for (int v : g[u]) {
    379     if (!used[v] && dist[u] < dist[v]) {
    380       dfs(v, g, dist, dp, used);
    381     }
    382 
    383     if (dist[u] < dist[v]) {
    384       dp[u] = min(dp[u], dp[v]);
    385     } else {
    386       dp[u] = min(dp[u], dist[v]);
    387     }
    388   }
    389 }
    390 
    391 void solve() {
    392   int n, m;
    393   cin >> n >> m;
    394   vector<vector<int>> g(n + 1);
    395   for (int i = 0; i < m; i++) {
    396     int u, v;
    397     cin >> u >> v;
    398     g[u].push_back(v);
    399   }
    400 
    401   vector<int> dist = calcDist(g);
    402   vector<int> dp(n + 1);
    403   vector<bool> used(n + 1);
    404   dfs(1, g, dist, dp, used);
    405   for (int i = 1; i <= n; i++) {
    406     cout << dp[i] << " ";
    407   }
    408   cout << endl;
    409 }
    410 
    411 int main() {
    412   int tests;
    413   cin >> tests;
    414   while (tests-- > 0) {
    415     solve();
    416   }
    417   return 0;
    418 }
    419 ```