1622.md (6380B)
1 Source: https://codeforces.com/blog/entry/98453 2 3 [1622A - Construct a Rectangle](/contest/1622/problem/A "Educational Codeforces Round 120 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 vector<int> l(3); 23 for (int i = 0; i < 3; ++i) 24 cin >> l[i]; 25 bool ok = false; 26 for (int i = 0; i < 3; ++i) 27 ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3]; 28 for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0) 29 ok |= l[(i + 1) % 3] == l[(i + 2) % 3]; 30 cout << (ok ? "YES\n" : "NO\n"); 31 } 32 } 33 ``` 34 35 [1622B - Berland Music](/contest/1622/problem/B "Educational Codeforces Round 120 (Rated for Div. 2)") 36 37 Idea: [adedalic](/profile/adedalic "International Master adedalic") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (awoo)** 44 45 ``` 46 for _ in range(int(input())): 47 n = int(input()) 48 p = [int(x) for x in input().split()] 49 s = input() 50 l = sorted([[s[i], p[i], i] for i in range(n)]) 51 q = [-1 for i in range(n)] 52 for i in range(n): 53 q[l[i][2]] = i + 1 54 print(*q) 55 ``` 56 57 [1622C - Set or Decrease](/contest/1622/problem/C "Educational Codeforces Round 120 (Rated for Div. 2)") 58 59 Idea: [adedalic](/profile/adedalic "International Master adedalic") 60 61 **Tutorial** 62 63 Tutorial is loading... 64 65 **Solution (adedalic)** 66 67 ``` 68 #include<bits/stdc++.h> 69 70 using namespace std; 71 72 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 73 #define sz(a) int((a).size()) 74 75 typedef long long li; 76 77 const int INF = int(1e9); 78 const li INF64 = li(1e18); 79 80 int n; 81 li k; 82 vector<int> a; 83 84 inline bool read() { 85 if(!(cin >> n >> k)) 86 return false; 87 a.resize(n); 88 fore (i, 0, n) 89 cin >> a[i]; 90 return true; 91 } 92 93 li accurateFloor(li a, li b) { 94 li val = a / b; 95 while (val * b > a) 96 val--; 97 return val; 98 } 99 100 inline void solve() { 101 sort(a.begin(), a.end()); 102 vector<li> pSum(n + 1, 0); 103 fore (i, 0, n) 104 pSum[i + 1] = pSum[i] + a[i]; 105 106 li ans = 1e18; 107 fore (y, 0, n) { 108 //(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k 109 //a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1) 110 //x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1) 111 112 li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1); 113 ans = min(ans, y + max(0LL, x)); 114 } 115 cout << ans << endl; 116 } 117 118 int main() { 119 #ifdef _DEBUG 120 freopen("input.txt", "r", stdin); 121 #endif 122 ios_base::sync_with_stdio(false); 123 cin.tie(0), cout.tie(0); 124 125 int t; cin >> t; 126 while (t--) { 127 read(); 128 solve(); 129 } 130 return 0; 131 } 132 ``` 133 134 [1622D - Shuffle](/contest/1622/problem/D "Educational Codeforces Round 120 (Rated for Div. 2)") 135 136 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 137 138 **Tutorial** 139 140 Tutorial is loading... 141 142 **Solution (BledDest)** 143 144 ``` 145 #include <bits/stdc++.h> 146 147 using namespace std; 148 149 const int MOD = 998244353; 150 151 int add(int x, int y) 152 { 153 x += y; 154 while(x >= MOD) x -= MOD; 155 while(x < 0) x += MOD; 156 return x; 157 } 158 159 int main() 160 { 161 int n; 162 cin >> n; 163 int k; 164 cin >> k; 165 string s; 166 cin >> s; 167 vector<int> p(n + 1); 168 for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0'); 169 vector<vector<int>> C(n + 1); 170 for(int i = 0; i <= n; i++) 171 { 172 C[i].resize(i + 1); 173 C[i][0] = C[i][i] = 1; 174 for(int j = 1; j < i; j++) 175 C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); 176 } 177 int ans = 1; 178 for(int i = 0; i < n; i++) 179 for(int j = i + 1; j < n; j++) 180 { 181 int cnt = j + 1 - i; 182 int cnt1 = p[j + 1] - p[i]; 183 if(cnt1 > k || p[n] < k) continue; 184 cnt -= 2; 185 if(s[i] == '0') cnt1--; 186 if(s[j] == '0') cnt1--; 187 if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0) 188 ans = add(ans, C[cnt][cnt1]); 189 } 190 cout << ans << endl; 191 } 192 ``` 193 194 [1622E - Math Test](/contest/1622/problem/E "Educational Codeforces Round 120 (Rated for Div. 2)") 195 196 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 197 198 **Tutorial** 199 200 Tutorial is loading... 201 202 **Solution (Neon)** 203 204 ``` 205 #include <bits/stdc++.h> 206 207 using namespace std; 208 209 #define forn(i, n) for (int i = 0; i < int(n); ++i) 210 211 int main() { 212 int t; 213 scanf("%d", &t); 214 while (t--) { 215 int n, m; 216 scanf("%d%d", &n, &m); 217 vector<int> x(n); 218 forn(i, n) scanf("%d", &x[i]); 219 vector<vector<int>> a(n, vector<int>(m)); 220 forn(i, n) forn(j, m) scanf("%1d", &a[i][j]); 221 222 int ans = -1; 223 vector<int> best; 224 forn(mask, 1 << n) { 225 vector<int> val(m); 226 forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1; 227 int res = 0; 228 forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i]; 229 vector<int> p(m); 230 iota(p.begin(), p.end(), 0); 231 sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; }); 232 forn(i, m) res += val[p[i]] * (i + 1); 233 if (res > ans) ans = res, best = p; 234 } 235 236 vector<int> ansPerm(m); 237 forn(i, m) ansPerm[best[i]] = i; 238 forn(i, m) printf("%d ", ansPerm[i] + 1); 239 puts(""); 240 } 241 } 242 ``` 243 244 [1622F - Quadratic Set](/contest/1622/problem/F "Educational Codeforces Round 120 (Rated for Div. 2)") 245 246 Idea: [Neon](/profile/Neon "Candidate Master Neon") 247 248 **Tutorial** 249 250 Tutorial is loading... 251 252 **Solution (Neon)** 253 254 ``` 255 #include <bits/stdc++.h> 256 257 using namespace std; 258 259 const int N = 1000 * 1000 + 13; 260 261 using li = unsigned long long; 262 263 int pr[N]; 264 li hs[N], f[N]; 265 unordered_map<li, int> rf; 266 267 int main() { 268 int n; 269 scanf("%d", &n); 270 271 mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); 272 iota(pr, pr + N, 0); 273 for (int i = 2; i <= n; ++i) if (pr[i] == i) { 274 for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i); 275 hs[i] = rnd(); 276 } 277 for (int i = 2; i <= n; ++i) { 278 f[i] = f[i - 1]; 279 int x = i; 280 while (x != 1) { 281 f[i] ^= hs[pr[x]]; 282 x /= pr[x]; 283 } 284 rf[f[i]] = i; 285 } 286 287 auto solve = [&] (int n) -> vector<int> { 288 li fp = 0; 289 for (int i = 2; i <= n; ++i) fp ^= f[i]; 290 if (fp == 0) return {}; 291 if (rf.count(fp)) return {rf[fp]}; 292 for (int i = 2; i <= n; ++i) { 293 li x = f[i] ^ fp; 294 if (rf.count(x) && rf[x] != i) return {rf[x], i}; 295 } 296 return {2, n / 2, n}; 297 }; 298 299 auto ans = solve(n); 300 printf("%d\n", n - (int)ans.size()); 301 for (int i = 1; i <= n; ++i) 302 if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i); 303 puts(""); 304 } 305 ```