codeforces-scrape

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

1765.md (24335B)


      1 Source: https://codeforces.com/blog/entry/109642
      2 
      3 [1765A - Access Levels](/contest/1765/problem/A "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
      4 
      5 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 #define forn(i, n) for (int i = 0; i < int(n); i++)
     17 
     18 using namespace std;
     19 
     20 int n, m, m2;
     21 vector<vector<char>> g;
     22 
     23 int T;
     24 vector<int> mt;
     25 vector<int> used;
     26 
     27 bool try_kuhn(int v){
     28     if (used[v] == T)
     29         return false;
     30     used[v] = T;
     31     forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
     32         mt[u] = v;
     33         return true;
     34     }
     35     return false;
     36 }
     37 
     38 int main() {
     39     cin >> n >> m;
     40     vector<string> b(m, string(n, '0'));
     41     forn(i, n){
     42         string t;
     43         cin >> t;
     44         forn(j, m) b[j][i] = t[j];
     45     }
     46     
     47     vector<string> nw = b;
     48     sort(nw.begin(), nw.end());
     49     nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
     50     m2 = nw.size();
     51     g.assign(m2, vector<char>(m2, 0));
     52     forn(i, m2) forn(j, m2) if (i != j){
     53         bool in = true;
     54         forn(k, n) in &= nw[i][k] >= nw[j][k];
     55         if (in) g[i][j] = 1;
     56     }
     57     
     58     mt.assign(m2, -1);
     59     used.assign(m2, -1);
     60     T = 0;
     61     int k = m2;
     62     forn(i, m2) if (try_kuhn(i)){
     63         ++T;
     64         --k;
     65     }
     66     
     67     vector<int> nxt(m2, -1);
     68     vector<char> st(m2, true);
     69     forn(i, m2) if (mt[i] != -1){
     70         nxt[mt[i]] = i;
     71         st[i] = false;
     72     }
     73     
     74     vector<int> gr(m2), req(m2);
     75     int t = 0;
     76     forn(i, m2) if (st[i]){
     77         int v = i;
     78         int pos = 2;
     79         while (v != -1){
     80             gr[v] = t;
     81             req[v] = pos;
     82             ++pos;
     83             v = nxt[v];
     84         }
     85         ++t;
     86     }
     87     assert(t == k);
     88     
     89     vector<int> num(m);
     90     forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
     91     
     92     printf("%d\n", k);
     93     forn(i, m) printf("%d ", gr[num[i]] + 1);
     94     puts("");
     95     forn(i, m) printf("%d ", req[num[i]]);
     96     puts("");
     97     forn(i, n){
     98         vector<int> l(k, 1);
     99         forn(j, m2) if (nw[j][i] == '1')
    100             l[gr[j]] = max(l[gr[j]], req[j]);
    101         forn(j, k)
    102             printf("%d ", l[j]);
    103         puts("");
    104     }
    105     return 0;
    106 }
    107 ```
    108 
    109 [1765B - Broken Keyboard](/contest/1765/problem/B "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    110 
    111 Idea: [vovuh](/profile/vovuh "Мастер vovuh"), preparation: [vovuh](/profile/vovuh "Мастер vovuh")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (vovuh)**
    118 
    119 ```
    120 for _ in range(int(input())):
    121     n = int(input())
    122     s = input()
    123     print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')
    124 ```
    125 
    126 [1765C - Card Guessing](/contest/1765/problem/C "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    127 
    128 Idea: [DStepanenko](/profile/DStepanenko "Эксперт DStepanenko"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    129 
    130 **Tutorial**
    131 
    132 Tutorial is loading...
    133 
    134 **Solution (awoo)**
    135 
    136 ```
    137 #include <bits/stdc++.h>
    138 
    139 #define forn(i, n) for (int i = 0; i < int(n); i++)
    140 #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
    141 
    142 using namespace std;
    143 
    144 const int MOD = 998244353;
    145 
    146 int add(int a, int b){
    147     a += b;
    148     if (a >= MOD)
    149         a -= MOD;
    150     return a;
    151 }
    152 
    153 int mul(int a, int b){
    154     return a * 1ll * b % MOD;
    155 }
    156 
    157 int binpow(int a, int b){
    158     int res = 1;
    159     while (b){
    160         if (b & 1)
    161             res = mul(res, a);
    162         a = mul(a, a);
    163         b >>= 1;
    164     }
    165     return res;
    166 }
    167 
    168 int main() {
    169     int n, k;
    170     scanf("%d%d", &n, &k);
    171     
    172     vector<int> fact(4 * n + 1);
    173     fact[0] = 1;
    174     fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
    175     vector<int> rfact(4 * n + 1);
    176     rfact.back() = binpow(fact.back(), MOD - 2);
    177     for (int i = int(fact.size()) - 2; i >= 0; --i)
    178         rfact[i] = mul(rfact[i + 1], i + 1);
    179     
    180     auto cnk = [&](int n, int k){
    181         return mul(fact[n], mul(rfact[k], rfact[n - k]));
    182     };
    183     
    184     vector<vector<int>> sv(n + 1, vector<int>(5));
    185     forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
    186     
    187     vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
    188     forn(ii, n + 1){
    189         int i = ii & 1;
    190         int ni = i ^ 1;
    191         dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
    192         for (int t = 1; t <= 4; ++t)
    193             dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
    194         forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
    195             dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
    196             for (int t = 1; p + t <= 4; ++t)
    197                 dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
    198         }
    199     }
    200     
    201     int ans = 0;
    202     forn(sum, k + 1){
    203         ans = add(ans, mul(mul(mul(
    204             sum < k ? 1 : 4 * n - k, 
    205             dp[(n & 1) ^ 1][sum][4]), 
    206             mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))), 
    207             mul(fact[4], fact[sum]))
    208         );
    209     }
    210     
    211     printf("%d\n", ans);
    212     return 0;
    213 }
    214 ```
    215 
    216 [1765D - Watch the Videos](/contest/1765/problem/D "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    217 
    218 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [DmitryKlenov](/profile/DmitryKlenov "Эксперт DmitryKlenov")
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution (DmitryKlenov)**
    225 
    226 ```
    227 #include <iostream>
    228 #include <algorithm>
    229 using namespace std;
    230 
    231 #define N 200000
    232 
    233 int a[N], n, s;
    234 
    235 bool can(int x) {
    236     int l = x - 1, r = n - 1;
    237     while (l < r) {
    238         if (a[r] > s - a[l]) return false;
    239         ++l;
    240         if (l < r) {
    241             if (a[l] > s - a[r]) return false;
    242             --r;
    243         }
    244     }
    245     return true;
    246 }
    247 
    248 int main() {
    249     long long sum = 0;
    250     scanf("%d %d\n", &n, &s);
    251     for(int i = 0; i < n; ++i) {
    252         scanf("%d", &a[i]);
    253         sum += a[i];
    254     }
    255 
    256     sort(a, a + n, greater<int>());
    257 
    258     int l = 1, r = n;
    259     while (l < r) {
    260         int m = (l + r) >> 1;
    261         if (can(m)) r = m;
    262         else l = m + 1;
    263     }
    264 
    265     long long ans = sum + r;
    266     cout << ans << endl;
    267 
    268     return 0;
    269 }
    270 ```
    271 
    272 [1765E - Exchange](/contest/1765/problem/E "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    273 
    274 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    275 
    276 **Tutorial**
    277 
    278 Tutorial is loading...
    279 
    280 **Solution (BledDest)**
    281 
    282 ```
    283 #include <bits/stdc++.h>
    284  
    285 using namespace std;
    286 
    287 void solve() 
    288 {
    289     int n, a, b;
    290     cin >> n >> a >> b;
    291     int x = (n + a - 1) / a;
    292     if(a > b) x = 1;
    293     cout << x << endl;
    294 }
    295 
    296 int main()
    297 {
    298     int t;
    299     cin >> t;
    300     for(int i = 0; i < t; i++)
    301         solve();
    302 }
    303 ```
    304 
    305 [1765F - Chemistry Lab](/contest/1765/problem/F "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    306 
    307 Idea: [awoo](/profile/awoo "Гроссмейстер awoo"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
    308 
    309 **Tutorial**
    310 
    311 Tutorial is loading...
    312 
    313 **Solution (awoo)**
    314 
    315 ```
    316 #include <bits/stdc++.h>
    317 
    318 #define forn(i, n) for (int i = 0; i < int(n); i++)
    319 
    320 using namespace std;
    321 
    322 typedef long long li;
    323 
    324 const li INF64 = 1e18;
    325 
    326 struct base{
    327     int x, w, c;
    328 };
    329 
    330 li area(const base &a, const base &b){
    331     return (a.c + b.c) * li(abs(a.x - b.x));
    332 }
    333 
    334 int main() {
    335     int n, k;
    336     scanf("%d%d", &n, &k);
    337     vector<base> a(n);
    338     forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
    339     sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
    340     vector<li> dp(n, -INF64);
    341     li ans = 0;
    342     forn(i, n){
    343         dp[i] = max(dp[i], -a[i].w * 200ll);
    344         for (int j = i + 1; j < n; ++j)
    345             dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
    346         ans = max(ans, dp[i]);
    347     }
    348     printf("%.15Lf\n", ans / (long double)(200));
    349     return 0;
    350 }
    351 ```
    352 
    353 [1765G - Guess the String](/contest/1765/problem/G "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    354 
    355 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    356 
    357 **Tutorial**
    358 
    359 Tutorial is loading...
    360 
    361 **Solution (BledDest)**
    362 
    363 ```
    364 #include <bits/stdc++.h>     
    365 
    366 using namespace std;
    367 
    368 mt19937 rnd(42);
    369 uniform_int_distribution<int> d(1, 2);
    370 
    371 int ask(int t, int i)
    372 {
    373     cout << t << " " << i + 1 << endl;
    374     int x;
    375     cin >> x;
    376     return x;
    377 }
    378 
    379 void giveAnswer(const string& s)
    380 {
    381     cout << 0 << " " << s << endl;
    382     int x;
    383     cin >> x;
    384     assert(x == 1);
    385 }
    386 
    387 void guessOne(string& s, int i)
    388 {
    389     int res = ask(1, i);
    390     if(res == 0)
    391         s[i] = '1';
    392     else
    393         s[i] = s[res - 1];
    394 }
    395 
    396 char inv(char c)
    397 {
    398     if(c == '0') return '1';
    399     return '0';
    400 }
    401 
    402 void guessTwo(string& s, int i)
    403 {
    404     if(s[1] == '0')
    405     {
    406         if(d(rnd) == 1)
    407         {
    408             int res = ask(1, i);
    409             if(res >= 2)
    410             {
    411                 s[i] = s[res - 1];
    412                 s[i - 1] = s[res - 2];
    413             }
    414             else if(res == 1)
    415             {
    416                 s[i] = '0';
    417                 s[i - 1] = '1';
    418             }
    419             else
    420             {
    421                 s[i] = '1';
    422                 guessOne(s, i - 1);
    423             }
    424         }
    425         else
    426         {
    427             int res = ask(2, i);
    428             if(res >= 2)
    429             {
    430                 s[i] = inv(s[res - 1]);
    431                 s[i - 1] = inv(s[res - 2]);
    432             }
    433             else if(res == 1)
    434             {
    435                 s[i] = '1';
    436                 s[i - 1] = '0';
    437             }
    438             else
    439             {
    440                 s[i] = '0';
    441                 guessOne(s, i - 1);
    442             }
    443         }
    444     }
    445     else
    446     {
    447         if(d(rnd) == 1)
    448         {
    449             int res = ask(1, i);
    450             if(res >= 2)
    451             {
    452                 s[i] = s[res - 1];
    453                 s[i - 1] = s[res - 2];
    454             }
    455             else if(res == 1)
    456             {
    457                 s[i] = '0';
    458                 guessOne(s, i - 1);
    459             }
    460             else
    461             {
    462                 s[i] = '1';
    463                 s[i - 1] = '1';
    464             }
    465         }
    466         else
    467         {
    468             int res = ask(2, i);
    469             if(res >= 2)
    470             {
    471                 s[i] = inv(s[res - 1]);
    472                 s[i - 1] = inv(s[res - 2]);
    473             }
    474             else if(res == 1)
    475             {
    476                 s[i] = '1';
    477                 guessOne(s, i - 1);
    478             }
    479             else
    480             {
    481                 s[i] = '0';
    482                 s[i - 1] = '0';
    483             }
    484         }
    485     }
    486 }
    487 
    488 int main()
    489 {
    490     int t;
    491     cin >> t;
    492     for(int i = 0; i < t; i++)
    493     {
    494         int n;
    495         cin >> n;
    496         string s(n, '0');
    497         for(int j = 1; j < n; j += 2)
    498         {
    499             if(j == 1) guessOne(s, j);
    500             else guessTwo(s, j);
    501         }
    502         if(n % 2 == 1) guessOne(s, n - 1);
    503         giveAnswer(s);
    504     }
    505 }
    506 ```
    507 
    508 [1765H - Hospital Queue](/contest/1765/problem/H "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    509 
    510 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
    511 
    512 **Tutorial**
    513 
    514 Tutorial is loading...
    515 
    516 **Solution (Neon)**
    517 
    518 ```
    519 #include <bits/stdc++.h>
    520 
    521 using namespace std;
    522 
    523 int main() {
    524   ios::sync_with_stdio(false); cin.tie(0);
    525   int n, m;
    526   cin >> n >> m;
    527   vector<int> a(n);
    528   for (auto &x : a) cin >> x;
    529   vector<vector<int>> g(n);
    530   for (int i = 0; i < m; ++i) {
    531     int x, y;
    532     cin >> x >> y;
    533     g[y - 1].push_back(x - 1);
    534   }
    535     
    536   vector<int> ans(n, -1);
    537   for (int s = 0; s < n; ++s) {
    538     vector<int> deg(n);
    539     for (int i = 0; i < n; ++i) 
    540       for (int j : g[i]) ++deg[j];
    541     priority_queue<pair<int, int>> q;
    542     for (int v = 0; v < n; ++v)
    543       if (deg[v] == 0 && v != s)
    544         q.push({a[v], v});
    545     for (int i = n; i > 0; --i) {
    546       if (q.empty() || q.top().first < i) {
    547         if (deg[s] == 0 && i <= a[s])
    548           ans[s] = i;
    549         break;
    550       }
    551       int v = q.top().second;
    552       q.pop();
    553       for (int u : g[v]) {
    554         --deg[u];
    555         if (deg[u] == 0 && u != s)
    556           q.push({a[u], u});
    557       }
    558     }
    559   }
    560   
    561   for (int &x : ans) cout << x << ' ';
    562 }
    563 ```
    564 
    565 [1765I - Infinite Chess](/contest/1765/problem/I "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    566 
    567 Idea: [DmitryKlenov](/profile/DmitryKlenov "Эксперт DmitryKlenov"), preparation: [dmitryme](/profile/dmitryme "Не в рейтинге, dmitryme")
    568 
    569 **Tutorial**
    570 
    571 Tutorial is loading...
    572 
    573 **Solution (awoo)**
    574 
    575 ```
    576 #include <bits/stdc++.h>
    577 
    578 #define forn(i, n) for (int i = 0; i < int(n); i++)
    579 
    580 using namespace std;
    581 
    582 const string al = "KQRBN";
    583 
    584 const int INF = 1e9;
    585 
    586 struct mv{ int dx, dy; };
    587 struct piece{ int x, y, t; };
    588 struct seg{ int l, r; };
    589 struct pos{ int x, y; };
    590 
    591 bool operator <(const pos &a, const pos &b){
    592     if (a.x != b.x) return a.x < b.x;
    593     return a.y < b.y;
    594 }
    595 
    596 vector<vector<mv>> mvs({
    597     {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
    598     {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    599     {{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
    600     {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    601     {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
    602 });
    603 
    604 int main() {
    605     int sx, sy, fx, fy;
    606     cin >> sx >> sy >> fx >> fy;
    607     swap(sx, sy), swap(fx, fy);
    608     --sx, --fx;
    609     
    610     int k;
    611     cin >> k;
    612     vector<piece> a(k);
    613     forn(i, k){
    614         string t;
    615         cin >> t >> a[i].x >> a[i].y;
    616         swap(a[i].x, a[i].y);
    617         --a[i].x;
    618         a[i].t = al.find(t[0]);
    619     }
    620     
    621     sort(a.begin(), a.end(), [](const piece &a, const piece &b){
    622         if (a.x != b.x) return a.x < b.x;
    623         return a.y < b.y;
    624     });
    625     
    626     vector<int> base({sy, fy});
    627     forn(i, k) base.push_back(a[i].y);
    628     vector<int> ys;
    629     for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
    630         ys.push_back(i);
    631     sort(ys.begin(), ys.end());
    632     ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    633     
    634     vector<vector<char>> tk(8, vector<char>(ys.size()));
    635     forn(i, k){
    636         a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
    637         tk[a[i].x][a[i].y] = true;
    638     }
    639     sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
    640     fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
    641     
    642     vector<vector<char>> bad = tk;
    643     
    644     forn(i, k){
    645         int x = a[i].x, y = a[i].y;
    646         if (a[i].t == 0 || a[i].t == 4){
    647             for (auto it : mvs[a[i].t]){
    648                 int nx = x + it.dx;
    649                 int ny = y + it.dy;
    650                 if (0 <= nx && nx < 8)
    651                     bad[nx][ny] = true;
    652             }
    653         }
    654         else{
    655             for (auto it : mvs[a[i].t]){
    656                 for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
    657                     if (nx < 0 || nx >= 8) break;
    658                     if (ny < 0 || ny >= int(ys.size())) break;
    659                     if (tk[nx][ny]) break;
    660                     bad[nx][ny] = true;
    661                 }
    662             }
    663         }
    664     }
    665     
    666     vector<vector<int>> d(8, vector<int>(ys.size(), INF));
    667     vector<vector<pos>> p(8, vector<pos>(ys.size()));
    668     set<pair<int, pos>> q;
    669     d[sx][sy] = 0;
    670     q.insert({0, {sx, sy}});
    671     while (!q.empty()){
    672         int x = q.begin()->second.x;
    673         int y = q.begin()->second.y;
    674         q.erase(q.begin());
    675         if (x == fx && y == fy){
    676             cout << d[x][y] << endl;
    677             return 0;
    678         }
    679         for (int ny : {y - 1, y, y + 1}){
    680             if (ny < 0 || ny >= int(ys.size())) continue;
    681             int dy = max(1, abs(ys[y] - ys[ny]));
    682             for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
    683                 int nd = d[x][y] + dy;
    684                 if (d[nx][ny] > nd){
    685                     q.erase({d[nx][ny], {nx, ny}});
    686                     d[nx][ny] = nd;
    687                     p[nx][ny] = {x, y};
    688                     q.insert({d[nx][ny], {nx, ny}});
    689                 }
    690             }
    691         }
    692     }
    693     
    694     cout << -1 << endl;
    695     return 0;
    696 }
    697 ```
    698 
    699 [1765J - Hero to Zero](/contest/1765/problem/J "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    700 
    701 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    702 
    703 **Tutorial**
    704 
    705 Tutorial is loading...
    706 
    707 **Solution (BledDest)**
    708 
    709 ```
    710 #include<bits/stdc++.h>
    711 
    712 using namespace std;
    713 
    714 int main()
    715 {
    716     int n;
    717     scanf("%d", &n);
    718     vector<int> a(n), b(n);
    719     for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    720     for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    721     sort(a.begin(), a.end());
    722     sort(b.begin(), b.end());
    723     long long total = 0;
    724     for(int i = 0; i < n; i++)
    725     {
    726         total += n * 1ll * (a[i] + b[i]);
    727         total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
    728         total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
    729     }
    730     for(int i = 0; i < n; i++)
    731         total -= (n - 1) * 1ll * abs(a[i] - b[i]);
    732     cout << total << endl;
    733 }
    734 ```
    735 
    736 [1765K - Torus Path](/contest/1765/problem/K "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    737 
    738 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic")
    739 
    740 **Tutorial**
    741 
    742 Tutorial is loading...
    743 
    744 **Solution (adedalic)**
    745 
    746 ```
    747 #include<bits/stdc++.h>
    748 
    749 using namespace std;
    750 
    751 int n;
    752 vector< vector<int> > a;
    753 
    754 bool read() {
    755     if (!(cin >> n))
    756         return false;
    757     a.resize(n, vector<int>(n));
    758     for (int i = 0; i < n; i++) {
    759         for (int j = 0; j < n; j++)
    760             cin >> a[i][j];
    761     }
    762     return true;
    763 }
    764 
    765 void solve() {
    766     long long sum = 0;
    767     for (int i = 0; i < n; i++)
    768         sum += accumulate(a[i].begin(), a[i].end(), 0LL);
    769     
    770     int mn = a[0][n - 1];
    771     for (int i = 0; i < n; i++)
    772         mn = min(mn, a[i][n - 1 - i]);
    773     
    774     cout << sum - mn << endl;
    775 }
    776 
    777 int main() {
    778 #ifdef _DEBUG
    779     freopen("input.txt", "r", stdin);
    780     int tt = clock();
    781 #endif
    782     
    783     if(read()) {
    784         solve();
    785         
    786 #ifdef _DEBUG
    787         cerr << "TIME = " << clock() - tt << endl;
    788         tt = clock();
    789 #endif
    790     }
    791     return 0;
    792 }
    793 ```
    794 
    795 [1765L - Project Manager](/contest/1765/problem/L "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    796 
    797 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo")
    798 
    799 **Tutorial**
    800 
    801 Tutorial is loading...
    802 
    803 **Solution (awoo)**
    804 
    805 ```
    806 #include <bits/stdc++.h>
    807 
    808 #define forn(i, n) for (int i = 0; i < int(n); i++)
    809 
    810 using namespace std;
    811 
    812 const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
    813 
    814 int main() {
    815     cin.tie(0);
    816     iostream::sync_with_stdio(false);
    817     int n, m, k;
    818     cin >> n >> m >> k;
    819     vector<vector<char>> ds(n, vector<char>(7));
    820     forn(i, n){
    821         int t;
    822         cin >> t;
    823         forn(_, t){
    824             string s;
    825             cin >> s;
    826             ds[i][find(days, days + 7, s) - days] = true;
    827         }
    828     }
    829     vector<int> h(m);
    830     forn(i, m) cin >> h[i];
    831     vector<vector<int>> a(k);
    832     forn(i, k){
    833         int p;
    834         cin >> p;
    835         a[i].resize(p);
    836         forn(j, p){
    837             cin >> a[i][j];
    838             --a[i][j];
    839         }
    840     }
    841     int j = 0;
    842     vector<int> ans(k, -1), lst(k);
    843     int done = 0;
    844     vector<map<int, int>> cur(7);
    845     vector<set<int>> wk(n);
    846     forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
    847         ++cur[j][a[i][0]];
    848     forn(i, k)
    849         wk[a[i][0]].insert(i);
    850     for (int d = 1;; ++d){
    851         if (j < m && h[j] == d){
    852             ++j;
    853             continue;
    854         }
    855         int wd = (d - 1) % 7;
    856         vector<int> now, sv;
    857         for (auto it : cur[wd]) now.push_back(it.first);
    858         for (int x : now){
    859             forn(i, 7){
    860                 auto it = cur[i].find(x);
    861                 if (it != cur[i].end()){
    862                     if (it->second == 1)
    863                         cur[i].erase(it);
    864                     else
    865                         --it->second;
    866                 }
    867             }
    868             int y = *wk[x].begin();
    869             sv.push_back(y);
    870             wk[x].erase(wk[x].begin());
    871         }
    872         forn(i, now.size()){
    873             int y = sv[i];
    874             ++lst[y];
    875             if (lst[y] == int(a[y].size())){
    876                 ans[y] = d;
    877                 ++done;
    878                 continue;
    879             }
    880             wk[a[y][lst[y]]].insert(y);
    881             forn(j, 7) if (ds[a[y][lst[y]]][j])
    882                 ++cur[j][a[y][lst[y]]];
    883         }
    884         if (done == k) break;
    885     }
    886     forn(i, k) cout << ans[i] << " ";
    887     cout << endl;
    888 }
    889 ```
    890 
    891 [1765M - Minimum LCM](/contest/1765/problem/M "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    892 
    893 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
    894 
    895 **Tutorial**
    896 
    897 Tutorial is loading...
    898 
    899 **Solution (Neon)**
    900 
    901 ```
    902 #include <bits/stdc++.h>
    903 
    904 using namespace std;
    905 
    906 int main() {
    907   int t;
    908   cin >> t;
    909   while (t--) {
    910     int n;
    911     cin >> n;
    912     int a = 1;
    913     for (int g = 2; g * g <= n; ++g) {
    914       if (n % g == 0) {
    915         a = n / g;
    916         break;
    917       }
    918     }
    919     cout << a << ' ' << n - a << '\n';
    920   }
    921 }
    922 ```
    923 
    924 [1765N - Number Reduction](/contest/1765/problem/N "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)")
    925 
    926 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
    927 
    928 **Tutorial**
    929 
    930 Tutorial is loading...
    931 
    932 **Solution (Neon)**
    933 
    934 ```
    935 #include <bits/stdc++.h>
    936 
    937 using namespace std;
    938 
    939 int main() {
    940   ios::sync_with_stdio(false);
    941   cin.tie(0);
    942   
    943   int t;
    944   cin >> t;
    945   while (t--) {
    946     string x;
    947     cin >> x;
    948     int k;
    949     cin >> k;
    950     int n = x.size();
    951     vector<vector<int>> pos(10);
    952     for (int i = 0; i < n; ++i)
    953       pos[x[i] - '0'].push_back(i);
    954     for (int i = 0; i < 10; ++i)
    955       reverse(pos[i].begin(), pos[i].end());
    956     string ans;
    957     int lst = 0, len = n - k;
    958     for (int i = 0; i < len; ++i) {
    959       for (int d = (i == 0); d <= 9; ++d) {
    960         while (!pos[d].empty() && pos[d].back() < lst)
    961           pos[d].pop_back();
    962         if (!pos[d].empty() && pos[d].back() - lst <= k) {
    963           ans += d + '0';
    964           k -= pos[d].back() - lst;
    965           lst = pos[d].back() + 1;
    966           break;
    967         }
    968       }
    969     }
    970     cout << ans << '\n';
    971   }
    972 }
    973 ```