codeforces-scrape

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

2059.md (11734B)


      1 Source: https://codeforces.com/blog/entry/139094
      2 
      3 Thank you for participating! We hope you enjoyed our problems
      4 
      5 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
      6 
      7 ## [2059A - Milya and Two Arrays](/contest/2059/problem/A "Codeforces Round 1002 (Div. 2)")
      8 
      9 **Solution**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18  
     19 int a[55],b[55];
     20  
     21 void solve(){
     22     int n;cin>>n;
     23     set<int> sa,sb;
     24     for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);
     25     for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);
     26     if(sa.size()+sb.size()<4){
     27         cout<<"NO\n";
     28     }else{
     29         cout<<"YES\n";
     30     }
     31 }
     32  
     33 int main(){
     34     ios_base::sync_with_stdio(0);
     35     cin.tie(0);
     36  
     37     int t;cin>>t;
     38     while(t--){
     39         solve();
     40     }
     41  
     42     return 0;
     43 }
     44 ```
     45 
     46 ## [2059B - Cost of the Array](/contest/2059/problem/B "Codeforces Round 1002 (Div. 2)")
     47 
     48 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
     49 
     50 **Solution**
     51 
     52 Tutorial is loading...
     53 
     54 **Implementation**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 using namespace std;
     59  
     60 void solve() {
     61     int n, k;
     62     cin >> n >> k;
     63     k /= 2;
     64     vector<int> a(n);
     65     for (auto &it: a) cin >> it;
     66     if (2 * k == n) {
     67         for (int i = 1; i < n; i += 2) {
     68             if (a[i] != (i + 1) / 2) {
     69                 cout << (i + 1) / 2 << '\n';
     70                 return;
     71             }
     72         }
     73         cout << k + 1 << '\n';
     74     } else {
     75         for (int i = 1; i <= n - 2 * k + 1; i++) {
     76             if (a[i] != 1) {
     77                 cout << "1\n";
     78                 return;
     79             }
     80         }
     81         cout << "2\n";
     82     }
     83 }
     84  
     85 int main() {
     86     int T = 1;
     87     cin >> T;
     88     while (T--) {
     89         solve();
     90     }
     91 }
     92 ```
     93 
     94 ## [2059C - Customer Service](/contest/2059/problem/C "Codeforces Round 1002 (Div. 2)")
     95 
     96 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
     97 
     98 **Solution**
     99 
    100 Tutorial is loading...
    101 
    102 **Implementation**
    103 
    104 ```
    105 #include <bits/stdc++.h>
    106 using namespace std;
    107  
    108 const int N=305;
    109  
    110 int a[N][N],suff[N];
    111  
    112 void solve(){
    113     int n;cin>>n;
    114     for(int i=1;i<=n;i++){
    115         suff[i]=0;
    116         for(int j=1;j<=n;j++){
    117             cin>>a[i][j];
    118         }
    119     }
    120     for(int i=1;i<=n;i++){
    121         for(int j=n;j>=1;j--){
    122             if(a[i][j]!=1)break;
    123             suff[i]++;
    124         }
    125     }
    126     multiset<int> s;
    127     for(int i=1;i<=n;i++){
    128         s.insert(suff[i]);
    129     }
    130     int ans=1;
    131     while(!s.empty()){
    132         int cur=*s.begin();
    133         if(cur>=ans){
    134             ans++;
    135         }
    136         s.extract(cur);
    137     }
    138     cout<<min(ans,n)<<'\n';
    139 }
    140  
    141 int main(){
    142     ios_base::sync_with_stdio(0);
    143     cin.tie(0);
    144  
    145     int t;cin>>t;
    146     while(t--){
    147         solve();
    148     }
    149  
    150     return 0;
    151 }
    152 ```
    153 
    154 ## [2059D - Graph and Graph](/contest/2059/problem/D "Codeforces Round 1002 (Div. 2)")
    155 
    156 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
    157 
    158 **Solution**
    159 
    160 Tutorial is loading...
    161 
    162 **Implementation**
    163 
    164 ```
    165 #include "bits/stdc++.h"
    166 using namespace std;
    167  
    168 #define int long long
    169 #define eb emplace_back
    170  
    171 const int INF = 1e18;
    172  
    173 void solve() {
    174     int n, s1, s2;
    175     cin >> n >> s1 >> s2;
    176     s1--, s2--;
    177     vector<vector<int>> g1(n), g2(n);
    178     vector<bool> good(n);
    179     set<pair<int, int>> edges;
    180     int m1;
    181     cin >> m1;
    182     for (int i = 0; i < m1; i++) {
    183         int v, u;
    184         cin >> v >> u;
    185         v--, u--;
    186         if (v > u)
    187             swap(v, u);
    188         edges.insert({v, u});
    189         g1[v].eb(u);
    190         g1[u].eb(v);
    191     }
    192     int m2;
    193     cin >> m2;
    194     for (int i = 0; i < m2; i++) {
    195         int v, u;
    196         cin >> v >> u;
    197         v--, u--;
    198         if (v > u)
    199             swap(v, u);
    200         if (edges.find({v, u}) != edges.end())
    201             good[v] = true, good[u] = true;
    202         g2[v].eb(u);
    203         g2[u].eb(v);
    204     }
    205     vector<vector<int>> d(n, vector<int> (n, INF));
    206     d[s1][s2] = 0;
    207     set<pair<int, pair<int, int>>> st;
    208     st.insert({0, {s1, s2}});
    209     while (!st.empty()) {
    210         auto [v, u] = st.begin()->second;
    211         st.erase(st.begin());
    212         for (auto to1 : g1[v]) {
    213             for (auto to2 : g2[u]) {
    214                 int w = abs(to1 - to2);
    215                 if (d[to1][to2] > d[v][u] + w) {
    216                     st.erase({d[to1][to2], {to1, to2}});
    217                     d[to1][to2] = d[v][u] + w;
    218                     st.insert({d[to1][to2], {to1, to2}});
    219                 }
    220             }
    221         }
    222     }
    223     int ans = INF;
    224     for (int i = 0; i < n; i++) {
    225         if (!good[i])
    226             continue;
    227         ans = min(ans, d[i][i]);
    228     }
    229     if (ans == INF)
    230         ans = -1;
    231     cout << ans << '\n';
    232 }
    233  
    234 signed main() {
    235     //cout << fixed << setprecision(5);
    236     ios::sync_with_stdio(false);
    237     cin.tie(nullptr);
    238     int T = 1;
    239     cin >> T;
    240     //cin >> G;
    241     while (T--)
    242         solve();
    243     return 0;
    244 }
    245 ```
    246 
    247 ## [2059E1 - Stop Gaming (Easy Version)](/contest/2059/problem/E1 "Codeforces Round 1002 (Div. 2)")
    248 
    249 Author [shfs](/profile/shfs "Candidate Master shfs") and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
    250 
    251 **Hint 1**
    252 
    253 To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements?
    254 
    255 **Hint 2**
    256 
    257 These elements must form the initial array prefix and the final array subsequence.
    258 
    259 **Hint 3**
    260 
    261 What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array?
    262 
    263 **Solution**
    264 
    265 Tutorial is loading...
    266 
    267 **Implementation**
    268 
    269 ```
    270 #include "bits/stdc++.h"
    271 using namespace std;
    272  
    273 void solve() {
    274     int n, m;
    275     cin >> n >> m;
    276     vector<int> a(n * m + 1), b(n * m + 1);
    277     vector<deque<int>> mat(n + 1, deque<int> (m));
    278     for (int i = 1; i <= n; i++) {
    279         for (int j = 0; j < m; j++) {
    280             int ind = j + 1 + (i - 1) * m;
    281             mat[i][j] = ind;
    282             cin >> a[ind];
    283         }
    284     }
    285     for (int i = 1; i <= n * m; i++)
    286         cin >> b[i];
    287     map<int, int> mp;
    288     for (int i = 1; i <= n * m; i++)
    289         mp[b[i]] = i;
    290     vector<int> s(n * m + 1), pos(n * m + 1, -1);
    291     for (int i = 1; i <= n * m; i++) {
    292         if (mp.find(a[i]) != mp.end())
    293             pos[i] = mp[a[i]];
    294         else
    295             break;
    296     }
    297     pos[0] = 0;
    298     int skipped = 0, pref = 0;
    299     bool prev = true;
    300     for (int i = 1; i <= n * m; i++) {
    301         if (pos[i - 1] > pos[i])
    302             break;
    303         int d = pos[i] - pos[i - 1] - 1;
    304         if (prev)
    305             skipped += d;
    306         else if (d > 0)
    307             break;
    308         if (skipped >= m - 1)
    309             prev = true;
    310         else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
    311             prev = true;
    312         else
    313             prev = false;
    314         if (prev)
    315             pref = i;
    316     }
    317     cout << n * m - pref << '\n';
    318 }
    319  
    320 signed main() {
    321     ios::sync_with_stdio(false);
    322     cin.tie(nullptr);
    323     int T = 1;
    324     cin >> T;
    325     while (T--)
    326         solve();
    327     return 0;
    328 }
    329 ```
    330 
    331 ## [2059E2 - Stop Gaming (Hard Version)](/contest/2059/problem/E2 "Codeforces Round 1002 (Div. 2)")
    332 
    333 Author [shfs](/profile/shfs "Candidate Master shfs") and developer is [yunetive29](/profile/yunetive29 "Master yunetive29")
    334 
    335 **Solution**
    336 
    337 Tutorial is loading...
    338 
    339 **Implementation**
    340 
    341 ```
    342 #include <bits/stdc++.h>
    343 using namespace std;
    344 
    345 #define eb emplace_back
    346 #define int long long
    347 #define all(x) x.begin(), x.end()
    348 #define fi first
    349 #define se second
    350 
    351 const int INF = 1e9 + 1000;
    352  
    353 struct segtree {
    354     vector<pair<int, int>> tree;
    355     vector<int> ass;
    356     int size = 1;
    357  
    358     void init(vector<int> &a) {
    359         while (a.size() >= size) {
    360             size <<= 1;
    361         }
    362         tree.assign(2 * size, {});
    363         ass.assign(2 * size, 0);
    364         build(0, 0, size, a);
    365     }
    366  
    367     void build(int x, int lx, int rx, vector<int> &a) {
    368         if (rx - lx == 1) {
    369             tree[x].se = lx;
    370             if (lx < a.size()) {
    371                 tree[x].fi = a[lx];
    372             } else {
    373                 tree[x].fi = INF;
    374             }
    375             return;
    376         }
    377         int m = (lx + rx) / 2;
    378         build(2 * x + 1, lx, m, a);
    379         build(2 * x + 2, m, rx, a);
    380         tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    381     }
    382  
    383     void push(int x, int lx, int rx) {
    384         tree[x].fi += ass[x];
    385         if (rx - lx == 1) {
    386             ass[x] = 0;
    387             return;
    388         }
    389         ass[2 * x + 1] += ass[x];
    390         ass[2 * x + 2] += ass[x];
    391         ass[x] = 0;
    392     }
    393  
    394     void update(int l, int r, int val, int x, int lx, int rx) {
    395         push(x, lx,  rx);
    396         if (l <= lx && rx <= r) {
    397             ass[x] += val;
    398             push(x, lx, rx);
    399             return;
    400         }
    401         if (rx <= l || r <= lx) {
    402             return;
    403         }
    404         int m = (lx + rx) / 2;
    405         update(l, r, val, 2 * x + 1, lx, m);
    406         update(l, r, val, 2 * x + 2, m, rx);
    407         tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    408     }
    409  
    410     void update(int l, int r, int val) {
    411         update(l, r + 1, val, 0, 0, size);
    412     }
    413  
    414     int req(int x, int lx, int rx) {
    415         push(x, lx, rx);
    416         if (rx - lx == 1) {
    417             return tree[x].se;
    418         }
    419         int m = (lx + rx) / 2;
    420         push(2 * x + 1, lx, m);
    421         push(2 * x + 2, m, rx);
    422         if (tree[2 * x + 2].fi == 0) {
    423             return req(2 * x + 2, m, rx);
    424         } else {
    425             return req(2 * x + 1, lx, m);
    426         }
    427     }
    428  
    429     int req() {
    430         return req(0, 0, size);
    431     }
    432 };
    433  
    434 void solve() {
    435     int n, m;
    436     cin >> n >> m;
    437     vector<int> a(n * m + 1), b(n * m + 1);
    438     for (int i = 1; i <= n; i++) {
    439         for (int j = 0; j < m; j++) {
    440             int ind = j + 1 + (i - 1) * m;
    441             cin >> a[ind];
    442         }
    443     }
    444     for (int i = 1; i <= n * m; i++)
    445         cin >> b[i];
    446     map<int, int> mp;
    447     for (int i = 1; i <= n * m; i++)
    448         mp[b[i]] = i;
    449     vector<int> s(n * m + 1), pos(n * m + 1, -1);
    450     for (int i = 1; i <= n * m; i++) {
    451         if (mp.find(a[i]) != mp.end())
    452             pos[i] = mp[a[i]];
    453         else
    454             break;
    455     }
    456     pos[0] = 0;
    457     int skipped = 0, pref = 0;
    458     bool prev = true;
    459     for (int i = 1; i <= n * m; i++) {
    460         if (pos[i - 1] > pos[i])
    461             break;
    462         int d = pos[i] - pos[i - 1] - 1;
    463         if (prev)
    464             skipped += d;
    465         else if (d > 0)
    466             break;
    467         if (skipped >= m - 1)
    468             prev = true;
    469         else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
    470             prev = true;
    471         else
    472             prev = false;
    473         if (prev)
    474             pref = i;
    475     }
    476     for (int i = 1; i <= pref; i++) {
    477         s[i - 1] = pos[i] - pos[i - 1] - 1;
    478     }
    479     s[pref] = n * m - pos[pref];
    480  
    481     vector<pair<int, int>> ans;
    482  
    483     int res = 0;
    484     for (int i = 0; i <= n * m; i++) {
    485         res += s[i];
    486     }
    487     vector<int> ost(pref + 1);
    488     for (int i = 1; i <= pref; i++) {
    489         ost[i] = (m - i % m) % m;
    490     }
    491     for (int i = 0; i <= pref; i++) {
    492         if (s[i] == 0) {
    493             ost[i] = INF;
    494         }
    495     }
    496     vector<int> gol(pref + 1);
    497     gol[0] = 1;
    498     for (int i = 1; i <= pref; i++) {
    499         gol[i] = (i + m - 1) / m + 1;
    500     }
    501  
    502     segtree tree;
    503  
    504     tree.init(ost);
    505  
    506     for (int step = 0; step < res; step++) {
    507         int chel = tree.req();
    508         ans.eb(gol[chel], b[pos[chel] + s[chel]]);
    509         tree.update(chel + 1, pref, -1);
    510         s[chel]--;
    511         if (s[chel] == 0) {
    512             tree.update(chel, chel, INF);
    513         }
    514     }
    515  
    516     cout << ans.size() << '\n';
    517     for (auto [i, col] : ans) {
    518         cout << i << " " << col << '\n';
    519     }
    520 }
    521  
    522 signed main() {
    523     //cout << fixed << setprecision(5);
    524     ios::sync_with_stdio(false);
    525     cin.tie(nullptr);
    526     int T = 1;
    527     cin >> T;
    528     //cin >> G;
    529     while (T--)
    530         solve();
    531     return 0;
    532 }
    533 ```