codeforces-scrape

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

1407.md (6044B)


      1 Source: https://codeforces.com/blog/entry/82417
      2 
      3 [1407A — Ahahahahahahahaha](https://codeforces.com/contest/1407/problem/A)
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int main() {
     16     int t;
     17     cin >> t;
     18     while (t--) {
     19         int n;
     20         cin >> n;
     21         vector<int>a(n), ans;
     22         int cnt0 = 0;
     23         for (int i = 0; i < n; i++) {
     24             cin >> a[i];
     25             if (!a[i]) cnt0++;
     26         }
     27         int cnt1 = n - cnt0;
     28         if (cnt0 >= n / 2) {
     29             cout << cnt0 << '\n';
     30             for (int i = 0; i < cnt0; i++) cout << 0 << ' ';
     31         } else {
     32             cout << cnt1 - cnt1 % 2 << '\n';
     33             for (int i = 0; i < cnt1 - cnt1 % 2; i++) {
     34                 cout << 1 << ' ';
     35             }
     36         }
     37         cout << '\n';
     38     }
     39     return 0;
     40 }
     41 ```
     42 
     43 [1407B — Big Vova](https://codeforces.com/contest/1407/problem/B)
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 
     54 using namespace std;
     55 
     56 void solve() {
     57     int n;
     58     cin >> n;
     59     int a[n];
     60     int mi = 0;
     61     for (int i = 0; i < n; i++) {
     62         cin >> a[i];
     63         mi = (a[i] > a[mi] ? i : mi);
     64     }
     65     vector<int> b(n);
     66     b[0] = a[mi]; a[mi] = 0;
     67     int cg = b[0];
     68     for (int i = 1; i < n; i++) {
     69         int ci = 0, cans = 0;
     70         for (int j = 0; j < n; j++)
     71             if (a[j] && __gcd(a[j], cg) > cans) {
     72                 cans = __gcd(a[j], cg);
     73                 ci = j;
     74             }
     75         b[i] = a[ci];
     76         cg = cans;
     77         a[ci] = 0;
     78     }
     79     for (int i = 0; i < n; i++)
     80         cout << b[i] << ' ';
     81     cout << '\n';
     82 }
     83 
     84 int main() {
     85     int t;
     86     cin >> t;
     87     while (t--)
     88         solve();
     89     return 0;
     90 }
     91 ```
     92 
     93 [1407C — Chocolate Bunny](https://codeforces.com/contest/1407/problem/C)
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Solution**
    100 
    101 ```
    102 #include <bits/stdc++.h>
    103 using namespace std;
    104 int ask(int x, int y) {
    105     cout << "? " << x + 1 << ' ' << y + 1 << endl;
    106     int z;
    107     cin >> z;
    108     return z;
    109 }
    110 int main() {
    111     int n;
    112     cin >> n;
    113     vector<int>ans(n, -1);
    114     int mx = 0;
    115     for (int i = 1; i < n; i++) {
    116         int a = ask(mx, i);
    117         int b = ask(i, mx);
    118         if (a > b) {
    119             ans[mx] = a;
    120             mx = i;
    121         } else {
    122             ans[i] = b;
    123         }
    124     }
    125     ans[mx] = n;
    126     cout << "! ";
    127     for (int i = 0; i < n; i++) cout << ans[i] << ' ';
    128     cout << endl;
    129     return 0;
    130 }
    131 ```
    132 
    133 [1407D — Discrete Centrifugal Jumps](https://codeforces.com/contest/1407/problem/D)
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 using namespace std;
    144 const int INF = 1e9 + 1;
    145 const int maxn = 3e5 + 1;
    146 int h[maxn], dp[maxn], lge[maxn], lle[maxn], rge[maxn], rle[maxn];
    147 vector<int>jumps[maxn];
    148 int main() {
    149     int n;
    150     cin >> n;
    151     for (int i = 0; i < n; i++) {
    152         cin >> h[i];
    153         dp[i] = INF;
    154     }
    155     dp[0] = 0;
    156     vector<pair<int, int> >st;
    157     for (int i = 0; i < n; i++) { // the nearest greater from the left
    158         while (!st.empty() && st.back().first < h[i]) {
    159             st.pop_back();
    160         }
    161         if (st.empty()) lge[i] = -1;
    162         else lge[i] = st.back().second;
    163         st.push_back({h[i], i});
    164     }
    165     st.clear();
    166     for (int i = 0; i < n; i++) { // the nearest less from the left
    167         while (!st.empty() && st.back().first > h[i]) {
    168             st.pop_back();
    169         }
    170         if (st.empty()) lle[i] = -1;
    171         else lle[i] = st.back().second;
    172         st.push_back({h[i], i});
    173     }
    174     st.clear();
    175     for (int i = n - 1; i >= 0; i--) { // the nearest greater from the right
    176         while (!st.empty() && st.back().first < h[i]) {
    177             st.pop_back();
    178         }
    179         if (st.empty()) rge[i] = -1;
    180         else rge[i] = st.back().second;
    181         st.push_back({h[i], i});
    182     }
    183     st.clear();
    184     for (int i = n - 1; i >= 0; i--) { // the nearest less from the right
    185         while (!st.empty() && st.back().first > h[i]) {
    186             st.pop_back();
    187         }
    188         if (st.empty()) rle[i] = -1;
    189         else rle[i] = st.back().second;
    190         st.push_back({h[i], i});
    191     }
    192     st.clear();
    193     for (int i = 0; i < n; i++) {
    194         if (rle[i] != -1) jumps[i].push_back(rle[i]);
    195         if (rge[i] != -1) jumps[i].push_back(rge[i]);
    196         if (lle[i] != -1) jumps[lle[i]].push_back(i);
    197         if (lge[i] != -1) jumps[lge[i]].push_back(i);
    198     }
    199     for (int i = 0; i < n; i++) {
    200         for (int to : jumps[i]) {
    201             dp[to] = min(dp[to], dp[i] + 1);
    202         }
    203     }
    204     cout << dp[n - 1];
    205     return 0;
    206 }
    207 ```
    208 
    209 [1407E — Egor in the Republic of Dagestan](https://codeforces.com/contest/1407/problem/E)
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 const int maxn = 1e6 + 1;
    223 
    224 vector<int> bg[maxn], rg[maxn];
    225 int b[maxn], r[maxn], d[maxn], col[maxn];
    226 int n, m;
    227 
    228 int main() {
    229     ios_base::sync_with_stdio(0);
    230     cin.tie(0); cout.tie(0);
    231     cin >> n >> m;
    232     for (int i = 0; i < m; i++) {
    233         int u, v, t;
    234         cin >> u >> v >> t;
    235         --u; --v;
    236         if (!t) bg[v].push_back(u);
    237         else rg[v].push_back(u);
    238     }
    239     for (int i = 0; i < n; i++)
    240         d[i] = b[i] = r[i] = n;
    241     queue<int> q;
    242     q.push(n - 1);
    243     d[n - 1] = r[n - 1] = b[n - 1] = 0;
    244     while (!q.empty()) {
    245         int x = q.front();
    246         q.pop();
    247         for (auto to : bg[x]) {
    248             if (b[to] < n) continue;
    249             b[to] = d[x] + 1;
    250             if (max(b[to], r[to]) < n) {
    251                 q.push(to);
    252                 d[to] = max(b[to], r[to]);
    253             }
    254         }
    255         for (auto to : rg[x]) {
    256             if (r[to] < n) continue;
    257             r[to] = d[x] + 1;
    258             if (max(b[to], r[to]) < n) {
    259                 q.push(to);
    260                 d[to] = max(b[to], r[to]);
    261             }
    262         }
    263     }
    264     if (d[0] == n) cout << "-1\n";
    265     else cout << d[0] << '\n';
    266     for (int i = 0; i < n; i++) {
    267         if (b[i] > r[i]) col[i] = 0;
    268         else col[i] = 1;
    269         cout << col[i];
    270     }
    271     return 0;
    272 }
    273 ```