codeforces-scrape

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

1971.md (9988B)


      1 Source: https://codeforces.com/blog/entry/129364
      2 
      3 Thank you for participating!
      4 
      5 [1971A - My First Sorting Problem](/contest/1971/problem/A "Codeforces Round 944 (Div. 4)")
      6 
      7 Idea: [flamestorm](/profile/flamestorm "Master flamestorm")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17  
     18 using namespace std;
     19  
     20 const int MAX = 200'007;
     21 const int MOD = 1'000'000'007;
     22  
     23 void solve() {
     24 	int x, y;
     25 	cin >> x >> y;
     26 	cout << min(x, y) << ' ' << max(x, y) << '\n';	
     27 }
     28  
     29 int main() {
     30 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     31 	// solve();
     32 }
     33 ```
     34 
     35 [1971B - Different String](/contest/1971/problem/B "Codeforces Round 944 (Div. 4)")
     36 
     37 Idea: [flamestorm](/profile/flamestorm "Master flamestorm")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47  
     48 using namespace std;
     49  
     50 const int MAX = 200'007;
     51 const int MOD = 1'000'000'007;
     52  
     53 void solve() {
     54 	string s;
     55 	cin >> s;
     56 	bool ok = false;
     57 	for (int i = 1; i < (int)(s.length()); i++) {
     58 		if (s[i] != s[0]) {swap(s[i], s[0]); ok = true; break;}
     59 	}	
     60 	if (!ok) {
     61 		cout << "NO\n"; return;
     62 	}
     63 	cout << "YES\n";
     64 	cout << s << '\n';
     65 }
     66  
     67 int main() {
     68 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     69 	// solve();
     70 }
     71 ```
     72 
     73 [1971C - Clock and Strings](/contest/1971/problem/C "Codeforces Round 944 (Div. 4)")
     74 
     75 Idea: [flamestorm](/profile/flamestorm "Master flamestorm")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85  
     86 using namespace std;
     87  
     88 const int MAX = 200'007;
     89 const int MOD = 1'000'000'007;
     90  
     91 void solve() {
     92 	int a, b, c, d;
     93 	cin >> a >> b >> c >> d;
     94 	string s;
     95 	for (int i = 1; i <= 12; i++) {
     96 		if (i == a || i == b) {s += "a";}
     97 		if (i == c || i == d) {s += "b";}
     98 	}
     99 	cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n");
    100 }
    101  
    102 int main() {
    103 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    104 	// solve();
    105 }
    106 ```
    107 
    108 [1971D - Binary Cut](/contest/1971/problem/D "Codeforces Round 944 (Div. 4)")
    109 
    110 Idea: [flamestorm](/profile/flamestorm "Master flamestorm")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Solution**
    117 
    118 ```
    119 #include <bits/stdc++.h>
    120  
    121 using namespace std;
    122  
    123 const int MAX = 200'007;
    124 const int MOD = 1'000'000'007;
    125  
    126 void solve() {
    127 	string s;
    128 	cin >> s;
    129 	int res = 1;
    130 	bool ex = false;
    131 	for (int i = 0; i + 1 < (int)(s.size()); i++) {
    132 		res += (s[i] != s[i + 1]);
    133 		ex |= (s[i] == '0' && s[i + 1] == '1');
    134 	}
    135 	cout << res - ex << '\n';
    136 }
    137  
    138 int main() {
    139 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    140 	// solve();
    141 }
    142 ```
    143 
    144 [1971E - Find the Car](/contest/1971/problem/E "Codeforces Round 944 (Div. 4)")
    145 
    146 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution**
    153 
    154 ```
    155 #include <iostream>
    156 #include <algorithm>
    157 #include <vector>
    158 #include <array>
    159 #include <set>
    160 #include <map>
    161 #include <queue>
    162 #include <stack>
    163 #include <list>
    164 #include <chrono>
    165 #include <random>
    166 #include <cstdlib>
    167 #include <cmath>
    168 #include <ctime>
    169 #include <cstring>
    170 #include <iomanip>
    171 #include <bitset>
    172 #include <cassert>
    173 typedef long long  ll;
    174 using namespace std;
    175  
    176 void solve()
    177 {
    178     int n, k, q;
    179     cin >> n >> k >> q;
    180     vector<long long> a(k+1), b(k+1);
    181     a[0] = 0;
    182     b[0] = 0;
    183     for(int i = 1; i <= k; i++)
    184     {
    185         cin >> a[i];
    186     }
    187     for(int i = 1; i <= k; i++)
    188     {
    189         cin >> b[i];
    190     }
    191     for(int i = 0; i < q; i++)
    192     {
    193         long long c;
    194         cin >> c;
    195         int l = 0, r = k;
    196         while(l <= r)
    197         {
    198             int mid = l+r>>1;
    199             if(a[mid] > c)
    200             {
    201                 r = mid-1;
    202             }
    203             else
    204             {
    205                 l = mid+1;
    206             }
    207         }
    208         if(a[r] == c)
    209         {
    210             cout << b[r] << " ";
    211             continue;
    212         }
    213         long long ans = b[r] + (c-a[r])*(b[r+1]-b[r])/(a[r+1]-a[r]);
    214         cout << ans << " ";
    215     }
    216     cout << endl;
    217 }
    218  
    219 int32_t main(){
    220     int t = 1;
    221     cin >> t;
    222     while (t--) {
    223         solve();
    224     }
    225 }
    226 ```
    227 
    228 [1971F - Circle Perimeter](/contest/1971/problem/F "Codeforces Round 944 (Div. 4)")
    229 
    230 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution**
    237 
    238 ```
    239 #include <iostream>
    240 using namespace std;
    241  
    242 void solve()
    243 {
    244     long long r;
    245     cin >> r;
    246     long long height = r;
    247     long long ans = 0;
    248     for(long long i = 0; i <= r; i++)
    249     {
    250         while(i*i+height*height >= (r+1)*(r+1))
    251         {
    252             height--;
    253         }
    254         long long cop = height;
    255         while(i*i+cop*cop >= r*r && cop > 0)
    256         {
    257             cop--;
    258             ans++;
    259         }
    260     }
    261     cout << ans*4 << endl;
    262 }
    263  
    264 int32_t main(){
    265     int t = 1;
    266     cin >> t;
    267     while (t--) {
    268         solve();
    269     }
    270 }
    271 ```
    272 
    273 [1971G - XOUR](/contest/1971/problem/G "Codeforces Round 944 (Div. 4)")
    274 
    275 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    276 
    277 **Tutorial**
    278 
    279 Tutorial is loading...
    280 
    281 **Solution**
    282 
    283 ```
    284 #include <iostream>
    285 #include <algorithm>
    286 #include <vector>
    287 #include <map>
    288 #include <queue>
    289  
    290 using namespace std;
    291  
    292  
    293 void solve()
    294 {
    295     int n;
    296     cin >> n;
    297     vector<int> a(n);
    298     map<int, priority_queue<int>> mp;
    299     for(int i = 0; i < n; i++)
    300     {
    301         cin >> a[i];
    302         mp[a[i]>>2].push(-a[i]);
    303     }
    304     for(int i = 0; i < n; i++)
    305     {
    306         cout << -mp[a[i]>>2].top() << " ";
    307         mp[a[i]>>2].pop();
    308     }
    309     cout << endl;
    310 }
    311  
    312 int32_t main(){
    313     int t = 1;
    314     cin >> t;
    315     while (t--) {
    316         solve();
    317     }
    318 }
    319 ```
    320 
    321 [1971H - ±1](/contest/1971/problem/H "Codeforces Round 944 (Div. 4)")
    322 
    323 Idea: [flamestorm](/profile/flamestorm "Master flamestorm")
    324 
    325 **Tutorial**
    326 
    327 Tutorial is loading...
    328 
    329 **Solution**
    330 
    331 ```
    332 #include <bits/stdc++.h>
    333  
    334  
    335 #include <algorithm>
    336 #include <utility>
    337 #include <vector>
    338  
    339 namespace atcoder {
    340 namespace internal {
    341  
    342 template <class E> struct csr {
    343     std::vector<int> start;
    344     std::vector<E> elist;
    345     csr(int n, const std::vector<std::pair<int, E>>& edges)
    346         : start(n + 1), elist(edges.size()) {
    347         for (auto e : edges) {
    348             start[e.first + 1]++;
    349         }
    350         for (int i = 1; i <= n; i++) {
    351             start[i] += start[i - 1];
    352         }
    353         auto counter = start;
    354         for (auto e : edges) {
    355             elist[counter[e.first]++] = e.second;
    356         }
    357     }
    358 };
    359  
    360 // Reference:
    361 // R. Tarjan,
    362 // Depth-First Search and Linear Graph Algorithms
    363 struct scc_graph {
    364   public:
    365     scc_graph(int n) : _n(n) {}
    366  
    367     int num_vertices() { return _n; }
    368  
    369     void add_edge(int from, int to) { edges.push_back({from, {to}}); }
    370  
    371     // @return pair of (# of scc, scc id)
    372     std::pair<int, std::vector<int>> scc_ids() {
    373         auto g = csr<edge>(_n, edges);
    374         int now_ord = 0, group_num = 0;
    375         std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
    376         visited.reserve(_n);
    377         auto dfs = [&](auto self, int v) -> void {
    378             low[v] = ord[v] = now_ord++;
    379             visited.push_back(v);
    380             for (int i = g.start[v]; i < g.start[v + 1]; i++) {
    381                 auto to = g.elist[i].to;
    382                 if (ord[to] == -1) {
    383                     self(self, to);
    384                     low[v] = std::min(low[v], low[to]);
    385                 } else {
    386                     low[v] = std::min(low[v], ord[to]);
    387                 }
    388             }
    389             if (low[v] == ord[v]) {
    390                 while (true) {
    391                     int u = visited.back();
    392                     visited.pop_back();
    393                     ord[u] = _n;
    394                     ids[u] = group_num;
    395                     if (u == v) break;
    396                 }
    397                 group_num++;
    398             }
    399         };
    400         for (int i = 0; i < _n; i++) {
    401             if (ord[i] == -1) dfs(dfs, i);
    402         }
    403         for (auto& x : ids) {
    404             x = group_num - 1 - x;
    405         }
    406         return {group_num, ids};
    407     }
    408  
    409     std::vector<std::vector<int>> scc() {
    410         auto ids = scc_ids();
    411         int group_num = ids.first;
    412         std::vector<int> counts(group_num);
    413         for (auto x : ids.second) counts[x]++;
    414         std::vector<std::vector<int>> groups(ids.first);
    415         for (int i = 0; i < group_num; i++) {
    416             groups[i].reserve(counts[i]);
    417         }
    418         for (int i = 0; i < _n; i++) {
    419             groups[ids.second[i]].push_back(i);
    420         }
    421         return groups;
    422     }
    423  
    424   private:
    425     int _n;
    426     struct edge {
    427         int to;
    428     };
    429     std::vector<std::pair<int, edge>> edges;
    430 };
    431  
    432 }  // namespace internal
    433  
    434 }  // namespace atcoder
    435  
    436 #include <cassert>
    437 #include <vector>
    438  
    439 namespace atcoder {
    440  
    441 // Reference:
    442 // B. Aspvall, M. Plass, and R. Tarjan,
    443 // A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean
    444 // Formulas
    445 struct two_sat {
    446   public:
    447     two_sat() : _n(0), scc(0) {}
    448     two_sat(int n) : _n(n), _answer(n), scc(2 * n) {}
    449  
    450     void add_clause(int i, bool f, int j, bool g) {
    451         assert(0 <= i && i < _n);
    452         assert(0 <= j && j < _n);
    453         scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0));
    454         scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0));
    455     }
    456     bool satisfiable() {
    457         auto id = scc.scc_ids().second;
    458         for (int i = 0; i < _n; i++) {
    459             if (id[2 * i] == id[2 * i + 1]) return false;
    460             _answer[i] = id[2 * i] < id[2 * i + 1];
    461         }
    462         return true;
    463     }
    464     std::vector<bool> answer() { return _answer; }
    465  
    466   private:
    467     int _n;
    468     std::vector<bool> _answer;
    469     internal::scc_graph scc;
    470 };
    471  
    472 }  // namespace atcoder
    473  
    474  
    475 using namespace std;
    476 using namespace atcoder;
    477  
    478 void solve() {
    479 	int n;
    480 	cin >> n;
    481 	int b[3][n];
    482 	for (int i = 0; i < 3; i++) {
    483 		for (int j = 0; j < n; j++) {
    484 			cin >> b[i][j];
    485 		}
    486 	}
    487 	two_sat ts(n);
    488 	for (int j = 0; j < n; j++) {
    489 		for (int i = 0; i < 3; i++) {
    490 			int nxt = (i + 1) % 3;
    491 			ts.add_clause(abs(b[i][j]) - 1, b[i][j] > 0, abs(b[nxt][j]) - 1, b[nxt][j] > 0);
    492 		}
    493 	}
    494 	cout << (ts.satisfiable() ? "YES\n" : "NO\n");
    495 }
    496  
    497 int main() {
    498 	ios::sync_with_stdio(false);
    499 	cin.tie(nullptr);
    500 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    501 	// solve();
    502 }
    503 ```