1709.md (4855B)
1 Source: https://codeforces.com/blog/entry/105164 2 3 [1709A - Three Doors](/contest/1709/problem/A "Educational Codeforces Round 132 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 x = int(input()) 16 a = [0] + [int(x) for x in input().split()] 17 print("YES" if a[x] != 0 and a[a[x]] != 0 else "NO") 18 ``` 19 20 [1709B - Also Try Minecraft](/contest/1709/problem/B "Educational Codeforces Round 132 (Rated for Div. 2)") 21 22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (vovuh)** 29 30 ``` 31 n, m = map(int, input().split()) 32 a = list(map(int, input().split())) 33 l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)] 34 r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)] 35 for i in range(n - 1): 36 l[i + 1] += l[i] 37 r[i + 1] += r[i] 38 for _ in range(m): 39 s, t = map(int, input().split()) 40 if s < t: 41 print(l[t - 1] - l[s - 1]) 42 else: 43 print(r[s - 1] - r[t - 1]) 44 ``` 45 46 [1709C - Recover an RBS](/contest/1709/problem/C "Educational Codeforces Round 132 (Rated for Div. 2)") 47 48 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution (Neon)** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 int main() { 62 auto check = [](const string& s) { 63 int bal = 0; 64 for (char c : s) { 65 if (c == '(') ++bal; 66 if (c == ')') --bal; 67 if (bal < 0) return false; 68 } 69 return bal == 0; 70 }; 71 72 ios::sync_with_stdio(false); cin.tie(0); 73 int t; 74 cin >> t; 75 while (t--) { 76 string s; 77 cin >> s; 78 vector<int> pos; 79 int op = s.size() / 2, cl = s.size() / 2; 80 for (int i = 0; i < s.size(); ++i) { 81 if (s[i] == '?') pos.push_back(i); 82 if (s[i] == '(') --op; 83 if (s[i] == ')') --cl; 84 } 85 for (int i = 0; i < pos.size(); ++i) { 86 if (i < op) s[pos[i]] = '('; 87 else s[pos[i]] = ')'; 88 } 89 bool ok = true; 90 if (op > 0 && cl > 0) { 91 swap(s[pos[op - 1]], s[pos[op]]); 92 if (check(s)) ok = false; 93 } 94 cout << (ok ? "YES\n" : "NO\n"); 95 } 96 } 97 ``` 98 99 [1709D - Rorororobot](/contest/1709/problem/D "Educational Codeforces Round 132 (Rated for Div. 2)") 100 101 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 102 103 **Tutorial** 104 105 Tutorial is loading... 106 107 **Solution (awoo)** 108 109 ``` 110 #include <bits/stdc++.h> 111 112 #define forn(i, n) for (int i = 0; i < int(n); i++) 113 114 using namespace std; 115 116 int main() { 117 int n, m; 118 scanf("%d%d", &n, &m); 119 vector<int> a(m); 120 forn(i, m) scanf("%d", &a[i]); 121 122 int l = 0; 123 while ((1 << l) <= m) ++l; 124 vector<vector<int>> st(l, vector<int>(m)); 125 forn(i, m) st[0][i] = a[i]; 126 for (int j = 1; j < l; ++j) forn(i, m){ 127 st[j][i] = st[j - 1][i]; 128 if (i + (1 << (j - 1)) < m) 129 st[j][i] = max(st[j][i], st[j - 1][i + (1 << (j - 1))]); 130 } 131 vector<int> pw(m + 1, 0); 132 for (int i = 2; i <= m; ++i) pw[i] = pw[i / 2] + 1; 133 auto get = [&](int l, int r){ 134 if (l > r) swap(l, r); 135 ++r; 136 int len = pw[r - l]; 137 return max(st[len][l], st[len][r - (1 << len)]); 138 }; 139 140 int q; 141 scanf("%d", &q); 142 forn(_, q){ 143 int xs, ys, xf, yf, k; 144 scanf("%d%d%d%d%d", &xs, &ys, &xf, &yf, &k); 145 --xs, --ys, --xf, --yf; 146 if (ys % k != yf % k || xs % k != xf % k){ 147 puts("NO"); 148 continue; 149 } 150 int mx = (n - xs - 1) / k * k + xs; 151 puts(get(ys, yf) <= mx ? "YES" : "NO"); 152 } 153 return 0; 154 } 155 ``` 156 157 [1709E - XOR Tree](/contest/1709/problem/E "Educational Codeforces Round 132 (Rated for Div. 2)") 158 159 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Solution (Neon)** 166 167 ``` 168 #include <bits/stdc++.h> 169 170 using namespace std; 171 172 const int N = 200 * 1000 + 13; 173 174 int n; 175 int a[N], b[N]; 176 vector<int> g[N]; 177 set<int> vals[N]; 178 179 void init(int v, int p) { 180 b[v] = a[v]; 181 if (p != -1) b[v] ^= b[p]; 182 for (int u : g[v]) if (u != p) 183 init(u, v); 184 } 185 186 int ans; 187 188 void calc(int v, int p) { 189 bool bad = false; 190 vals[v].insert(b[v]); 191 for (int u : g[v]) if (u != p) { 192 calc(u, v); 193 if (vals[v].size() < vals[u].size()) vals[v].swap(vals[u]); 194 for (int x : vals[u]) bad |= vals[v].count(x ^ a[v]); 195 for (int x : vals[u]) vals[v].insert(x); 196 vals[u].clear(); 197 } 198 if (bad) { 199 ans += 1; 200 vals[v].clear(); 201 } 202 } 203 204 int main() { 205 ios::sync_with_stdio(false); cin.tie(0); 206 cin >> n; 207 for (int i = 0; i < n; ++i) cin >> a[i]; 208 for (int i = 0; i < n - 1; ++i) { 209 int x, y; 210 cin >> x >> y; 211 --x; --y; 212 g[x].push_back(y); 213 g[y].push_back(x); 214 } 215 init(0, -1); 216 calc(0, -1); 217 cout << ans << '\n'; 218 } 219 ``` 220 221 [1709F - Multiset of Strings](/contest/1709/problem/F "Educational Codeforces Round 132 (Rated for Div. 2)") 222 223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 224 225 **Tutorial** 226 227 Tutorial is loading...