codeforces-scrape

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

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 ```