754.md (11819B)
1 Source: https://codeforces.com/blog/entry/49637 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 #include <bits/stdc++.h> 9 10 using namespace std; 11 12 int main() { 13 int n; 14 scanf("%d", &n); 15 vector<int> a(n); 16 long long sum = 0; 17 for (int & x : a) { 18 scanf("%d", &x); 19 sum += x; 20 } 21 if (sum != 0) { 22 puts("YES"); 23 puts("1"); 24 printf("%d %d\n", 1, n); 25 exit(0); 26 } 27 sum = 0; 28 for (int i = 0; i < n; i++) { 29 sum += a[i]; 30 if (sum != 0) { 31 puts("YES"); 32 puts("2"); 33 printf("%d %d\n", 1, i + 1); 34 printf("%d %d\n", i + 2, n); 35 exit(0); 36 } 37 } 38 puts("NO"); 39 } 40 ``` 41 42 Tutorial is loading... 43 44 **Code** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 char str[4][4 + 1]; 53 // cells are '.', 'o', 'x' 54 for (int i = 0; i < 4; i++) { 55 cin >> str[i]; 56 } 57 58 auto check = [&]() { 59 for (int i = 0; i < 4; i++) { 60 for (int j = 0; j < 4; j++) { 61 for (int dx = -1; dx <= 1; dx++) { 62 for (int dy = -1; dy <= 1; dy++) { 63 if (dx == 0 && dy == 0) continue; 64 if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue; 65 bool ok = true; 66 for (int p = 0; p < 3; p++) { 67 ok &= str[i + p * dx][j + p * dy] == 'x'; 68 } 69 if (ok) return true; 70 } 71 } 72 } 73 } 74 return false; 75 }; 76 77 for (int i = 0; i < 4; i++) { 78 for (int j = 0; j < 4; j++) { 79 if (str[i][j] == '.') { 80 str[i][j] = 'x'; 81 if (check()) { 82 puts("YES"); 83 exit(0); 84 } 85 str[i][j] = '.'; 86 } 87 } 88 } 89 puts("NO"); 90 } 91 ``` 92 93 Tutorial is loading... 94 95 **Code** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 #define all(x) (x).begin(), (x).end() 103 104 void solve() { 105 int n; 106 cin >> n; 107 vector<string> names(n); 108 for (string& name : names) { 109 cin >> name; 110 } 111 sort(all(names)); 112 113 auto getIdx = [&](const string& s) { 114 int pos = lower_bound(all(names), s) - names.begin(); 115 if (pos == (int)names.size() || names[pos] != s) return -1; 116 return pos; 117 }; 118 119 auto splitIntoUserMessage = [](const string& s) { 120 size_t pos = s.find(':'); 121 assert(pos != string::npos); 122 return make_pair(s.substr(0, pos), s.substr(pos + 1)); 123 }; 124 125 auto splitIntoTokensOfLatinLetters = [](const string& s) { 126 vector<string> result; 127 string token; 128 for (char c : s) { 129 if (isalpha(c) || isdigit(c)) { 130 token += c; 131 } 132 else { 133 if (!token.empty()) { 134 result.push_back(token); 135 } 136 token.clear(); 137 } 138 } 139 if (!token.empty()) { 140 result.push_back(token); 141 } 142 return result; 143 }; 144 145 int m; 146 cin >> m; 147 vector<int> who(m); 148 vector<vector<char>> can(m, vector<char>(n, true)); 149 150 vector<string> messages(m); 151 152 string tmp; 153 getline(cin, tmp); 154 155 for (int i = 0; i < m; i++) { 156 string cur; 157 getline(cin, cur); 158 pair<string, string> p = splitIntoUserMessage(cur); 159 const string& user = p.first; 160 const string& message = p.second; 161 who[i] = getIdx(user); 162 if (who[i] != -1) { 163 fill(all(can[i]), false); 164 can[i][who[i]] = true; 165 } 166 messages[i] = message; 167 vector<string> tokens = splitIntoTokensOfLatinLetters(message); 168 for (const string& z : tokens) { 169 int idx = getIdx(z); 170 if (idx != -1) { 171 can[i][idx] = false; 172 } 173 } 174 } 175 176 vector<vector<int>> par(m, vector<int>(n, -1)); 177 for (int i = 0; i < n; i++) { 178 if (can[0][i]) par[0][i] = 0; 179 } 180 for (int msg = 0; msg + 1 < m; msg++) { 181 for (int i = 0; i < n; i++) { 182 if (par[msg][i] == -1) continue; 183 for (int j = 0; j < n; j++) { 184 if (i == j) continue; 185 if (can[msg + 1][j]) { 186 par[msg + 1][j] = i; 187 } 188 } 189 } 190 } 191 int msg = m - 1, pos = -1; 192 for (int i = 0; i < n; i++) { 193 if (par[msg][i] != -1) { 194 pos = i; 195 break; 196 } 197 } 198 if (pos == -1) { 199 cout << "Impossible\n"; 200 return; 201 } 202 while (msg >= 0) { 203 who[msg] = pos; 204 pos = par[msg][pos]; 205 msg--; 206 } 207 for (int i = 0; i < m; i++) { 208 cout << names[who[i]] << ":" << messages[i] << "\n"; 209 } 210 return; 211 } 212 213 int main() { 214 //freopen("input.txt", "r", stdin); 215 int t; 216 cin >> t; // number of tests 217 218 while (t--) { 219 solve(); 220 } 221 } 222 ``` 223 224 Tutorial is loading... 225 226 **Code** 227 228 ``` 229 #include <bits/stdc++.h> 230 231 using namespace std; 232 233 typedef long long ll; 234 235 int nextInt() { 236 int x = 0, p = 1; 237 char c; 238 do { 239 c = getchar(); 240 } while (c <= 32); 241 if (c == '-') { 242 p = -1; 243 c = getchar(); 244 } 245 while (c >= '0' && c <= '9') { 246 x = x * 10 + c - '0'; 247 c = getchar(); 248 } 249 return x * p; 250 } 251 252 #define all(x) (x).begin(), (x).end() 253 254 const int N = (int)3e5 + 5; 255 const int MAX_VAL = (int)1e9; 256 257 int n; 258 ll l[N], r[N]; 259 260 struct event { 261 ll x; 262 int c; 263 event() {} 264 event(ll x, int c) : x(x), c(c) {} 265 }; 266 267 pair<ll, int> check(ll len) { 268 if (len == 0) return make_pair(0LL, n); 269 static vector<event> evs; 270 evs.resize(0); 271 for (int i = 1; i <= n; i++) { 272 if (r[i] - len > l[i]) { 273 evs.push_back(event(l[i], 1)); 274 evs.push_back(event(r[i] - len, -1)); 275 } 276 } 277 sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; }); 278 reverse(all(evs)); 279 int cnt = 0, maxiCnt = 0; 280 ll bestPos = 0; 281 while (evs.size() > 0) { 282 ll x = evs.back().x; 283 while (evs.size() > 0 && evs.back().x == x) { 284 cnt += evs.back().c; 285 evs.pop_back(); 286 } 287 if (cnt > maxiCnt) { 288 maxiCnt = cnt; 289 bestPos = x; 290 } 291 } 292 return make_pair(bestPos, maxiCnt); 293 } 294 295 vector<int> getAns(ll len) { 296 if (len == 0) { 297 vector<int> res(n); 298 iota(all(res), 1); 299 return res; 300 } 301 ll pos = check(len).first; 302 vector<int> res; 303 for (int i = 1; i <= n; i++) { 304 if (pos >= l[i] && pos < r[i] - len) { 305 res.push_back(i); 306 } 307 } 308 return res; 309 } 310 311 int main() { 312 n = nextInt(); 313 int k = nextInt(); 314 for (int i = 1; i <= n; i++) { 315 l[i] = nextInt(); 316 r[i] = nextInt() + 2; 317 } 318 ll l = 0, r = MAX_VAL + MAX_VAL + 5; 319 while (r - l > 1) { 320 ll mid = (l + r) >> 1; 321 if (check(mid).second >= k) l = mid; 322 else r = mid; 323 } 324 325 vector<int> ans = getAns(l); 326 327 cout << l << endl; 328 assert((int)ans.size() >= k); 329 ans.resize(k); 330 for (int i : ans) { 331 printf("%d ", i); 332 } 333 puts(""); 334 } 335 ``` 336 337 Tutorial is loading... 338 339 **C++ code** 340 341 ``` 342 #include <bits/stdc++.h> 343 344 using namespace std; 345 346 const int N = (int)404; 347 const int ALPHA = 26; 348 349 bitset<N> b[ALPHA][N]; 350 char patt[N][N]; 351 bitset<N> result[N]; 352 353 bitset<N> getShifted(const bitset<N>& b, int len, int shift) { 354 assert(0 <= shift && shift < len); 355 return (b >> shift) | (b << (len - shift)); 356 } 357 358 int main() { 359 #ifdef LOCAL 360 freopen("input.txt", "r", stdin); 361 #endif 362 int n, m, r, c; 363 scanf("%d%d", &n, &m); 364 365 for (int i = 0; i < n; i++) { 366 static char str[N]; 367 scanf("%s", str); 368 for (int j = 0; j < m; j++) { 369 b[(int)(str[j] - 'a')][i][j] = true; 370 } 371 } 372 373 scanf("%d%d", &r, &c); 374 375 for (int i = 0; i < n; i++) { 376 result[i] = ~result[i]; 377 } 378 379 for (int i = 0; i < r; i++) { 380 scanf("%s", patt[i]); 381 for (int j = 0; j < c; j++) { 382 if (patt[i][j] == '?') continue; 383 int c = patt[i][j] - 'a'; 384 int shiftByX = (((-i) % n) + n) % n; 385 int shiftByY = (((j) % m) + m) % m; 386 for (int x = 0; x < n; x++) { 387 int nx = (x + shiftByX); 388 if (nx >= n) nx -= n; 389 result[nx] &= getShifted(b[c][x], m, shiftByY); 390 } 391 } 392 } 393 394 for (int i = 0; i < n; i++) { 395 for (int j = 0; j < m; j++) { 396 putchar(result[i][j] ? '1' : '0'); 397 } 398 puts(""); 399 } 400 } 401 ``` 402 403 **Java code** 404 405 ``` 406 import java.io.*; 407 import java.util.*; 408 409 public class Main { 410 411 static class InputReader { 412 BufferedReader bufferedReader; 413 StringTokenizer stringTokenizer; 414 InputReader(InputStream inputStream) { 415 bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768); 416 stringTokenizer = null; 417 } 418 String next() { 419 while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) { 420 try { 421 stringTokenizer = new StringTokenizer(bufferedReader.readLine()); 422 } catch (IOException ex) { 423 ex.printStackTrace(); 424 throw new RuntimeException(ex); 425 } 426 } 427 return stringTokenizer.nextToken(); 428 } 429 int nextInt() { 430 return Integer.parseInt(next()); 431 } 432 long nextLong() { 433 return Long.parseLong(next()); 434 } 435 double nextDouble() { 436 return Double.parseDouble(next()); 437 } 438 } 439 440 static int[] newBitSet(int n) { 441 return new int[(n + 31) / 32]; 442 } 443 444 static void setBit(int[] a, int pos) { 445 a[pos >>> 5] |= (1 << (pos & 31)); 446 } 447 448 static boolean getBit(int[] a, int pos) { 449 return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0; 450 } 451 452 static void setAll(int[] a) { 453 for (int i = 0; i < a.length; i++) { 454 a[i] = ~0; 455 } 456 } 457 458 static void resetAll(int[] a) { 459 for (int i = 0; i < a.length; i++) { 460 a[i] = 0; 461 } 462 } 463 464 static void andXYtoX(int[] x, int[] y) { 465 for (int i = 0; i < x.length; i++) { 466 x[i] &= y[i]; 467 } 468 } 469 470 static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) { 471 int[] z = shl[ch][shift & 31][x]; 472 int delta = (shift >>> 5); 473 for (int i = delta; i < to.length; i++) { 474 to[i - delta] |= z[i]; 475 } 476 } 477 478 static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) { 479 int[] z = shr[ch][shift & 31][x]; 480 int delta = (shift >>> 5); 481 for (int i = 0; i + delta < to.length; i++) { 482 to[i + delta] |= z[i]; 483 } 484 } 485 486 static void printBitset(int a[], int l, int r) { 487 for (int i = l; i <= r; i++) { 488 System.err.print(getBit(a, i) ? '1' : '0'); 489 } 490 System.err.println(); 491 } 492 493 static final int ALPHA = 26; 494 495 public static void main(String[] args) { 496 InputReader in = new InputReader(System.in); 497 PrintWriter out = new PrintWriter(System.out); 498 499 int n = in.nextInt(); 500 int m = in.nextInt(); 501 502 int[][][][] shl = new int[ALPHA][32][n][]; 503 int[][][][] shr = new int[ALPHA][32][n][]; 504 505 for (int c = 0; c < ALPHA; c++) { 506 for (int sh = 0; sh < 32; sh++) { 507 for (int i = 0; i < n; i++) { 508 shl[c][sh][i] = newBitSet(m); 509 shr[c][sh][i] = newBitSet(m); 510 } 511 } 512 } 513 514 String[] s = new String[n]; 515 516 for (int i = 0; i < n; i++) { 517 s[i] = in.next(); 518 for (int j = 0; j < m; j++) { 519 int c = s[i].charAt(j) - 'a'; 520 for (int sh = 0; sh < 32; sh++) { 521 if (j - sh >= 0) { 522 setBit(shl[c][sh][i], j - sh); 523 } 524 if (j + sh < m) { 525 setBit(shr[c][sh][i], j + sh); 526 } 527 } 528 } 529 } 530 531 int r = in.nextInt(); 532 int c = in.nextInt(); 533 534 String[] patt = new String[r]; 535 536 int[][] res = new int[n][]; 537 538 for (int i = 0; i < n; i++) { 539 res[i] = newBitSet(m); 540 setAll(res[i]); 541 } 542 543 int[] tmp = newBitSet(m); 544 545 for (int i = 0; i < r; i++) { 546 patt[i] = in.next(); 547 for (int j = 0; j < c; j++) { 548 if (patt[i].charAt(j) == '?') continue; 549 int cur = patt[i].charAt(j) - 'a'; 550 int shiftByX = (((-i) % n) + n) % n; 551 int shiftByY = (((j) % m) + m) % m; 552 553 for (int x = 0; x < n; x++) { 554 int nx = x + shiftByX; 555 if (nx >= n) nx -= n; 556 resetAll(tmp); 557 leftShiftAndOr(cur, shiftByY, x, shl, tmp); 558 rightShiftAndOr(cur, m - shiftByY, x, shr, tmp); 559 andXYtoX(res[nx], tmp); 560 } 561 } 562 } 563 564 for (int i = 0; i < n; i++) { 565 for (int j = 0; j < m; j++) { 566 out.print(getBit(res[i], j) ? '1' : '0'); 567 } 568 out.println(); 569 } 570 571 out.close(); 572 } 573 } 574 ```