codeforces-scrape

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

1619.md (10867B)


      1 Source: https://codeforces.com/blog/entry/98159
      2 
      3 [1619A - Квадратная строка?](/contest/1619/problem/A "Codeforces Round 762 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, 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 #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         string s;
     25         cin >> s;
     26         bool ok = true;
     27         if (s.length() % 2 == 0) {
     28             forn(i, s.length() / 2)
     29                 if (s[i] != s[i + s.length() / 2])
     30                     ok = false;
     31         } else
     32             ok = false;
     33         cout << (ok ? "YES" : "NO") << endl;
     34     }
     35 }
     36 ```
     37 
     38 [1619B - Квадраты и кубы](/contest/1619/problem/B "Codeforces Round 762 (Div. 3)")
     39 
     40 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50  
     51 using namespace std;
     52  
     53 #define forn(i, n) for (int i = 0; i < int(n); i++)
     54  
     55 int main() {
     56     int t;
     57     cin >> t;
     58     forn(tt, t) {
     59         int n;
     60         cin >> n;
     61         set<int> a;
     62         for (int i = 1; i * i <= n; i++)
     63             a.insert(i * i);
     64         for (int i = 1; i * i * i <= n; i++)
     65             a.insert(i * i * i);
     66         cout << a.size() << endl;
     67     }
     68 }
     69 ```
     70 
     71 [1619C - Неправильное сложение](/contest/1619/problem/C "Codeforces Round 762 (Div. 3)")
     72 
     73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
     74 
     75 **Tutorial**
     76 
     77 Tutorial is loading...
     78 
     79 **Solution**
     80 
     81 ```
     82 #include<bits/stdc++.h>
     83 #define len(s) (int)s.size()
     84 using namespace std;
     85 using ll = long long;
     86  
     87 void solve(){
     88     ll a, s;
     89     cin >> a >> s;
     90     vector<int>b;
     91     while(s){
     92         int x = a % 10;
     93         int y = s % 10;
     94         if(x <= y) b.emplace_back(y - x);
     95         else{
     96             s /= 10;
     97             y += 10 * (s % 10);
     98             if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x);
     99             else{
    100                 cout << -1 << '\n';
    101                 return;
    102             }
    103         }
    104         a /= 10;
    105         s /= 10;
    106     }
    107     if(a) cout << -1 << '\n';
    108     else{
    109         while (b.back() == 0) b.pop_back();
    110         for(int i = len(b) - 1; i >= 0; i--) cout << b[i];
    111         cout << '\n';
    112     }
    113 }
    114  
    115 int main(){
    116     ios_base ::sync_with_stdio(false);
    117     cin.tie(nullptr);
    118  
    119     int t;
    120     cin >> t;
    121     while (t){
    122         solve();
    123         t--;
    124     }
    125     return 0;
    126 }
    127 ```
    128 
    129 [1619D - Новогодняя задача](/contest/1619/problem/D "Codeforces Round 762 (Div. 3)")
    130 
    131 Idea: [Vladosiya](/profile/Vladosiya "Специалист Vladosiya")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Solution**
    138 
    139 ```
    140 //
    141 // Created by Vlad on 17.12.2021.
    142 //
    143  
    144 #include <bits/stdc++.h>
    145  
    146 #define int long long
    147 #define mp make_pair
    148 #define x first
    149 #define y second
    150 #define all(a) (a).begin(), (a).end()
    151 #define rall(a) (a).rbegin(), (a).rend()
    152  
    153 /*#pragma GCC optimize("Ofast")
    154 #pragma GCC optimize("no-stack-protector")
    155 #pragma GCC optimize("unroll-loops")
    156 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
    157 #pragma GCC optimize("fast-math")
    158 */
    159 typedef long double ld;
    160 typedef long long ll;
    161  
    162 using namespace std;
    163  
    164 mt19937 rnd(143);
    165  
    166 const int inf = 1e10;
    167 const int M = 998244353;
    168 const ld pi = atan2(0, -1);
    169 const ld eps = 1e-4;
    170  
    171 int n, m;
    172 vector<vector<int>> p;
    173  
    174 bool check(int x){
    175     vector<bool> abl(m);
    176     bool pair = false;
    177     for(int i = 0; i < n; ++i){
    178         int c = 0;
    179         for(int j = 0; j < m; ++j){
    180             if(p[i][j] >= x){
    181                 abl[j] = true;
    182                 c++;
    183             }
    184         }
    185         if(c > 1) pair = true;
    186     }
    187     if(!pair && m > 1) return false;
    188     bool ans = true;
    189     for(bool b: abl){
    190         ans = ans && b;
    191     }
    192     return ans;
    193 }
    194  
    195 void solve() {
    196     cin >> n >> m;
    197     p.assign(n, vector<int>(m));
    198     for(int i = 0; i < n; ++i){
    199         for(int j = 0; j < m; ++j){
    200             cin >> p[i][j];
    201         }
    202     }
    203     int l = 1, r = 2;
    204     while (check(r)) r *= 2;
    205     while (r - l > 1){
    206         int mid = (r + l) / 2;
    207         if(check(mid)) l = mid;
    208         else r = mid;
    209     }
    210     cout << l;
    211 }
    212  
    213 bool multi = true;
    214  
    215 signed main() {
    216     //freopen("in.txt", "r", stdin);
    217     //freopen("in.txt", "w", stdout);
    218     int t = 1;
    219     if (multi) {
    220         cin >> t;
    221     }
    222     for (; t != 0; --t) {
    223         solve();
    224         cout << "\n";
    225     }
    226     return 0;
    227 }
    228 ```
    229 
    230 [1619E - MEX и инкременты](/contest/1619/problem/E "Codeforces Round 762 (Div. 3)")
    231 
    232 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Мастер ibraevdmitriy")
    233 
    234 **Tutorial**
    235 
    236 Tutorial is loading...
    237 
    238 **Solution**
    239 
    240 ```
    241 #include <iostream>
    242 #include <vector>
    243 #include <stack>
    244 #include <algorithm>
    245  
    246 using namespace std;
    247  
    248 typedef long long ll;
    249 const int MAX_N = 2e5;
    250  
    251 int main() {
    252     int t;
    253     cin >> t;
    254     for (int _ = 0; _ < t; ++_) {
    255         int n;
    256         cin >> n;
    257         vector<int> a(n), cnt(n + 1);
    258         for (int i = 0; i < n; ++i) {
    259             cin >> a[i];
    260             cnt[a[i]]++;
    261         }
    262         sort(a.begin(), a.end());
    263         stack<int> st;
    264         vector<ll> ans(n + 1, -1);
    265         ll sum = 0;
    266         for (int i = 0; i <= n; ++i) {
    267             if (i > 0 && cnt[i - 1] == 0) {
    268                 if (st.empty()) {
    269                     break;
    270                 }
    271                 int j = st.top();
    272                 st.pop();
    273                 sum += i - j - 1;
    274             }
    275             ans[i] = sum + cnt[i];
    276             while (i > 0 && cnt[i - 1] > 1) {
    277                 cnt[i - 1]--;
    278                 st.push(i - 1);
    279             }
    280         }
    281         for (ll x : ans) {
    282             cout << x << ' ';
    283         }
    284         cout << '\n';
    285     }
    286 }
    287 ```
    288 
    289 [1619F - Сыграем в Шляпу?](/contest/1619/problem/F "Codeforces Round 762 (Div. 3)")
    290 
    291 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution**
    298 
    299 ```
    300 #include <bits/stdc++.h>
    301  
    302 using namespace std;
    303  
    304 #define forn(i, n) for (int i = 0; i < int(n); i++)
    305  
    306 int main() {
    307     int t;
    308     cin >> t;
    309     forn(tt, t) {
    310         int n, m, k;
    311         cin >> n >> m >> k;
    312         vector<int> p(n);
    313         forn(i, n)
    314             p[i] = i;
    315         if (tt > 0)
    316             cout << endl;
    317         forn(round, k) {
    318             int index = 0;
    319             forn(table, m) {
    320                 int size = n / m;
    321                 if (table < n % m)
    322                     size++;
    323                 cout << size;
    324                 forn(j, size)
    325                     cout << " " << p[index++] + 1;
    326                 cout << endl;                        
    327             }
    328             rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
    329         }
    330     }
    331 }
    332 ```
    333 
    334 [1619G - Необычный сапёр](/contest/1619/problem/G "Codeforces Round 762 (Div. 3)")
    335 
    336 Idea: [Gol_D](/profile/Gol_D "Кандидат в мастера Gol_D")
    337 
    338 **Tutorial**
    339 
    340 Tutorial is loading...
    341 
    342 **Solution**
    343 
    344 ```
    345 #include <bits/stdc++.h>
    346  
    347 using namespace std;
    348  
    349 typedef long long ll;
    350  
    351 #define forn(i, n) for (int i = 0; i < int(n); i++)
    352  
    353 int k;
    354  
    355 map <int, vector<int>> mx;
    356 map <int, vector<int>> my;
    357 map <pair<int ,int>, bool> used;
    358 map <pair<int, int>, int> time_of;
    359  
    360 int dfs(int x, int y) {
    361     used[{x, y}] = true;
    362     int _min_ = time_of[{x, y}];
    363  
    364     auto i = lower_bound(mx[x].begin(), mx[x].end(), y);
    365     auto j = lower_bound(my[y].begin(), my[y].end(), x);
    366  
    367     if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) {
    368         _min_ = min(_min_, dfs(x, *i));
    369     }
    370     --i;
    371     if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) {
    372         _min_ = min(_min_, dfs(x, *i));
    373     }
    374  
    375     if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) {
    376         _min_ = min(_min_, dfs(*j, y));
    377     }
    378     --j;
    379     if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) {
    380         _min_ = min(_min_, dfs(*j, y));
    381     }
    382  
    383     return _min_;
    384 }
    385  
    386 void solve() {
    387     mx.clear();
    388     my.clear();
    389     used.clear();
    390  
    391     int n;
    392     cin >> n >> k;
    393     vector <pair<int, int>> a(n);
    394     int x, y, timer;
    395  
    396     for (int i = 0; i < n; ++i) {
    397         cin >> x >> y >> timer;
    398         a[i] = {x, y};
    399         time_of[{x, y}] = timer;
    400         mx[x].push_back(y);
    401         my[y].push_back(x);
    402     }
    403     vector<int> res;
    404  
    405     for (auto now: mx) {
    406         sort(mx[now.first].begin(), mx[now.first].end());
    407     }
    408     for (auto now: my) {
    409         sort(my[now.first].begin(), my[now.first].end());
    410     }
    411  
    412     for (auto now: a) {
    413         if (!used[now]) {
    414             res.push_back(dfs(now.first, now.second));
    415         }
    416     }
    417     sort(res.begin(), res.end());
    418  
    419     int ans = res.size() - 1;
    420     for (int i = 0; i < res.size(); ++i) {
    421         ans = min(ans, max((int)res.size() - i - 2, res[i]));
    422     }
    423     cout << ans << '\n';
    424 }
    425 int main() {
    426     ios_base::sync_with_stdio(0);
    427     cin.tie(nullptr); cout.tie(nullptr);
    428     int tests;
    429     cin >> tests;
    430     forn(tt, tests) {
    431         solve();
    432     }
    433 }
    434 ```
    435 
    436 [1619H - Перестановка и запросы](/contest/1619/problem/H "Codeforces Round 762 (Div. 3)")
    437 
    438 Idea: [Brovko](/profile/Brovko "Международный мастер Brovko")
    439 
    440 **Tutorial**
    441 
    442 Tutorial is loading...
    443 
    444 **Solution**
    445 
    446 ```
    447 #include <bits/stdc++.h>
    448 //#define int long long
    449 #define ld long double
    450 #define x first
    451 #define y second
    452 #define pb push_back
    453  
    454 using namespace std;
    455 const int Q = 100;
    456  
    457 int n, q, p[100005], r[100005], a[100005];
    458  
    459 int32_t main()
    460 {
    461     ios_base::sync_with_stdio(0);
    462     cin.tie(0);
    463     cout.tie(0);
    464  
    465     cin >> n >> q;
    466  
    467     for(int i = 0; i < n; i++)
    468     {
    469         cin >> p[i];
    470         p[i]--;
    471     }
    472  
    473     for(int i = 0; i < n; i++)
    474         r[p[i]] = i;
    475  
    476     for(int i = 0; i < n; i++)
    477     {
    478         int x = i;
    479  
    480         for(int j = 0; j < Q; j++)
    481             x = p[x];
    482  
    483         a[i] = x;
    484     }
    485  
    486     while(q--)
    487     {
    488         int t, x, y;
    489         cin >> t >> x >> y;
    490  
    491         if(t == 2)
    492         {
    493             x--;
    494  
    495             while(y >= Q)
    496             {
    497                 y -= Q;
    498                 x = a[x];
    499             }
    500  
    501             while(y--)
    502                 x = p[x];
    503  
    504             cout << x + 1 << "\n";
    505         }
    506         else
    507         {
    508             x--;
    509             y--;
    510  
    511             swap(r[p[x]], r[p[y]]);
    512             swap(p[x], p[y]);
    513  
    514             int ax = x;
    515  
    516             for(int i = 0; i < Q; i++)
    517                 ax = p[ax];
    518  
    519             int x2 = x;
    520  
    521             for(int i = 0; i < Q; i++)
    522             {
    523                 a[x] = ax;
    524                 x = r[x];
    525                 ax = r[ax];
    526             }
    527  
    528             swap(x, y);
    529  
    530             ax = x;
    531  
    532             for(int i = 0; i < Q; i++)
    533                 ax = p[ax];
    534  
    535             x2 = x;
    536  
    537             for(int i = 0; i < Q; i++)
    538             {
    539                 a[x] = ax;
    540                 x = r[x];
    541                 ax = r[ax];
    542             }
    543         }
    544     }
    545 }
    546 ```