codeforces-scrape

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

1721.md (8551B)


      1 Source: https://codeforces.com/blog/entry/106416
      2 
      3 [1721A - Image](/contest/1721/problem/A "Educational Codeforces Round 134 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main()
     19 {
     20     int t;
     21     cin >> t;
     22     for(int i = 0; i < t; i++)
     23     {
     24         string s1, s2;
     25         cin >> s1 >> s2;
     26         s1 += s2;
     27         cout << set<char>(s1.begin(), s1.end()).size() - 1 << endl;
     28     }
     29 }
     30 ```
     31 
     32 [1721B - Deadly Laser](/contest/1721/problem/B "Educational Codeforces Round 134 (Rated for Div. 2)")
     33 
     34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (awoo)**
     41 
     42 ```
     43 for _ in range(int(input())):
     44 	n, m, sx, sy, d = map(int, input().split())
     45 	if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d:
     46 	    print(-1)
     47 	else:
     48 	    print(n + m - 2)
     49 ```
     50 
     51 [1721C - Min-Max Array Transformation](/contest/1721/problem/C "Educational Codeforces Round 134 (Rated for Div. 2)")
     52 
     53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (adedalic)**
     60 
     61 ```
     62 fun main() {
     63     repeat(readLine()!!.toInt()) {
     64         val n = readLine()!!.toInt()
     65         val a = readLine()!!.split(' ').map { it.toInt() }
     66         val b = readLine()!!.split(' ').map { it.toInt() }
     67 
     68         val indices = (0 until n).sortedBy { a[it] }
     69         val mn = Array(n) { 0 }
     70         val mx = Array(n) { 0 }
     71 
     72         var lst = n
     73         for (i in n - 1 downTo 0) {
     74             val pos = indices[i]
     75             mn[pos] = lowerBound(b, a[pos])
     76             mx[pos] = lst - 1;
     77             if (i == mn[pos])
     78                 lst = i
     79 
     80             mn[pos] = b[mn[pos]] - a[pos]
     81             mx[pos] = b[mx[pos]] - a[pos]
     82         }
     83         println(mn.joinToString(" "))
     84         println(mx.joinToString(" "))
     85     }
     86 }
     87 
     88 fun lowerBound(a: List<Int>, v: Int): Int {
     89     var l = -1; var r = a.size
     90     while (r - l > 1) {
     91         val m = (l + r) / 2
     92         if (a[m] < v)
     93             l = m
     94         else
     95             r = m
     96     }
     97     return r
     98 }
     99 ```
    100 
    101 [1721D - Maximum AND](/contest/1721/problem/D "Educational Codeforces Round 134 (Rated for Div. 2)")
    102 
    103 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution (Neon)**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 
    116 int main() {
    117   ios::sync_with_stdio(false); cin.tie(0);
    118   int t;
    119   cin >> t;
    120   while (t--) {
    121     int n;
    122     cin >> n;
    123     vector<int> a(n), b(n);
    124     for (int& x : a) cin >> x;
    125     for (int& x : b) cin >> x;
    126     
    127     auto check = [&](int ans) {
    128       map<int, int> cnt;
    129       for (int x : a) ++cnt[x & ans];
    130       for (int x : b) --cnt[~x & ans];
    131       bool ok = true;
    132       for (auto it : cnt) ok &= it.second == 0;
    133       return ok;
    134     };
    135     
    136     int ans = 0;
    137     for (int bit = 29; bit >= 0; --bit) 
    138       if (check(ans | (1 << bit)))
    139         ans |= 1 << bit;
    140     
    141     cout << ans << '\n';
    142   }
    143 }
    144 ```
    145 
    146 [1721E - Prefix Function Queries](/contest/1721/problem/E "Educational Codeforces Round 134 (Rated for Div. 2)")
    147 
    148 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    149 
    150 **Tutorial**
    151 
    152 Tutorial is loading...
    153 
    154 **Solution (awoo)**
    155 
    156 ```
    157 #include <bits/stdc++.h>
    158 
    159 #define forn(i, n) for (int i = 0; i < int(n); i++)
    160 
    161 using namespace std;
    162 
    163 const int AL = 26;
    164 
    165 vector<int> prefix_function(const string &s){
    166 	int n = s.size();
    167 	vector<int> p(n);
    168 	for (int i = 1; i < n; ++i){
    169 		int k = p[i - 1];
    170 		while (k > 0 && s[i] != s[k])
    171 			k = p[k - 1];
    172 		k += (s[i] == s[k]);
    173 		p[i] = k;
    174 	}
    175 	return p;
    176 }
    177 
    178 int main() {
    179 	cin.tie(0);
    180 	iostream::sync_with_stdio(false);
    181 	string s;
    182 	cin >> s;
    183 	int n = s.size();
    184 	auto p = prefix_function(s);
    185 	vector<vector<int>> A(n, vector<int>(AL));
    186 	forn(i, n) forn(j, AL){
    187 		if (i > 0 && j != s[i] - 'a')
    188 			A[i][j] = A[p[i - 1]][j];
    189 		else
    190 			A[i][j] = i + (j == s[i] - 'a');
    191 	}
    192 	int q;
    193 	cin >> q;
    194 	vector<vector<int>> ans(q);
    195 	forn(z, q){
    196 		string t;
    197 		cin >> t;
    198 		int m = t.size();
    199 		s += t;
    200 		for (int i = n; i < n + m; ++i){
    201 		    A.push_back(vector<int>(AL));
    202 			forn(j, AL){
    203 				if (j != s[i] - 'a')
    204 					A[i][j] = A[p[i - 1]][j];
    205 				else
    206 					A[i][j] = i + (j == s[i] - 'a');
    207 			}
    208 			p.push_back(A[p[i - 1]][s[i] - 'a']);
    209 			ans[z].push_back(p[i]);
    210 		}
    211 		forn(_, m){
    212 			p.pop_back();
    213 			s.pop_back();
    214 			A.pop_back();
    215 		}
    216 	}
    217 	for (auto &it : ans){
    218 		for (int x : it)
    219 			cout << x << ' ';
    220 		cout << '\n';
    221 	}
    222 	return 0;
    223 }
    224 ```
    225 
    226 [1721F - Matching Reduction](/contest/1721/problem/F "Educational Codeforces Round 134 (Rated for Div. 2)")
    227 
    228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Solution (BledDest)**
    235 
    236 ```
    237 #include<bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 const int N = 400043;
    242 const int INF = int(1e9);
    243 
    244 struct edge
    245 {
    246     int y, c, f;
    247     edge() {};
    248     edge(int y, int c, int f) : y(y), c(c), f(f) {};
    249 };
    250 
    251 vector<edge> e;
    252 vector<int> g[N];
    253 int S, T, V;
    254 int d[N], lst[N];
    255 int n1, n2, m, q;
    256 map<pair<int, int>, int> es;
    257 
    258 void add_edge(int x, int y, int c)
    259 {
    260     g[x].push_back(e.size());
    261     e.push_back(edge(y, c, 0));
    262     g[y].push_back(e.size());
    263     e.push_back(edge(x, 0, 0));
    264 }
    265 
    266 int rem(int x)
    267 {
    268     return e[x].c - e[x].f;
    269 }
    270 
    271 bool bfs()
    272 {
    273     for (int i = 0; i < V; i++)
    274         d[i] = INF;
    275     d[S] = 0;
    276     queue<int> q;
    277     q.push(S);
    278     while (!q.empty())
    279     {
    280         int k = q.front();
    281         q.pop();
    282         for (auto y : g[k])
    283         {
    284             if (rem(y) == 0)
    285                 continue;
    286             int to = e[y].y;
    287             if (d[to] > d[k] + 1)
    288             {
    289                 q.push(to);
    290                 d[to] = d[k] + 1;
    291             }
    292         }
    293     }
    294     return d[T] < INF;
    295 }
    296 
    297 int dfs(int x, int mx)
    298 {
    299     if (x == T || mx == 0)
    300         return mx;
    301     int sum = 0;
    302     for (; lst[x] < g[x].size(); lst[x]++)
    303     {
    304         int num = g[x][lst[x]];
    305         int r = rem(num);
    306         if (r == 0)
    307             continue;
    308         int to = e[num].y;
    309         if (d[to] != d[x] + 1)
    310             continue;
    311         int pushed = dfs(to, min(r, mx));
    312         if (pushed > 0)
    313         {
    314             e[num].f += pushed;
    315             e[num ^ 1].f -= pushed;
    316             sum += pushed;
    317             mx -= pushed;
    318             if (mx == 0)
    319                 return sum;
    320         }
    321     }
    322     return sum;
    323 }
    324 
    325 int Dinic()
    326 {
    327     int ans = 0;
    328     while (bfs())
    329     {
    330         for (int i = 0; i < V; i++)
    331             lst[i] = 0;
    332         int f = 0;
    333         do
    334         {
    335             f = dfs(S, INF);
    336             ans += f;
    337         } while (f > 0);
    338     }
    339     return ans;
    340 }
    341 
    342 int main()
    343 {
    344     scanf("%d %d %d %d", &n1, &n2, &m, &q);
    345     S = n1 + n2;
    346     T = S + 1;
    347     V = T + 1;
    348     for (int i = 0; i < m; i++)
    349     {
    350         int x, y;
    351         scanf("%d %d", &x, &y);
    352         --x;
    353         --y;
    354         es[make_pair(x, y)] = i + 1;
    355         add_edge(x, n1 + y, 1);
    356     }
    357     for (int i = 0; i < n1; i++)
    358         add_edge(S, i, 1);
    359     for (int i = 0; i < n2; i++)
    360         add_edge(i + n1, T, 1);
    361     Dinic();
    362     bfs();
    363     vector<int> vertex_cover;
    364     map<int, int> index;
    365     set<int> matched;
    366     long long sum = 0;
    367     for (int i = 0; i < n1; i++)
    368         if (d[i] == INF)
    369         {
    370             vertex_cover.push_back(i + 1);
    371             for (auto ei : g[i])
    372                 if (e[ei].f == 1)
    373                 {
    374                     int idx = es[make_pair(i, e[ei].y - n1)];
    375                     index[i + 1] = idx;
    376                     sum += idx;
    377                     matched.insert(idx);
    378                 }
    379         }
    380     for (int i = 0; i < n2; i++)
    381         if (d[i + n1] != INF)
    382         {
    383             vertex_cover.push_back(-(i + 1));
    384             for (auto ei : g[i + n1])
    385                 if (e[ei].f == -1)
    386                 {
    387                     int idx = es[make_pair(e[ei].y, i)];
    388                     index[-(i + 1)] = idx;
    389                     sum += idx;    
    390                     matched.insert(idx);
    391                 }
    392         }
    393     for (int i = 0; i < q; i++)
    394     {
    395         int s;
    396         scanf("%d", &s);
    397         if (s == 1)
    398         {
    399             puts("1");
    400             int v = vertex_cover.back();
    401             vertex_cover.pop_back();
    402             printf("%d\n", v);
    403             sum -= index[v];
    404             matched.erase(index[v]);
    405             printf("%lld\n", sum);
    406         }
    407         else
    408         {
    409             printf("%d\n", (int)matched.size());
    410             for(auto x : matched) printf("%d ", x);
    411             puts("");
    412         }   
    413         fflush(stdout);
    414     }
    415 }
    416 ```