codeforces-scrape

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

1106.md (6663B)


      1 Source: https://codeforces.com/blog/entry/64928
      2 
      3 Tutorial is loading...
      4 
      5 **Code**
      6 
      7 ```
      8 #include <bits/stdc++.h>
      9 #define N 510
     10 using namespace std;
     11 
     12 char a[N][N];
     13 int n;
     14 int main(){
     15 	scanf("%d", &n);
     16 	for (int i = 1; i <= n; i++){
     17 		scanf("%s", a[i] + 1);
     18 	}
     19 	
     20 	int ans = 0;
     21 	for (int i = 2; i < n; i++){
     22 		for (int j = 2; j < n; j++){
     23 			if (a[i][j] == 'X' && a[i - 1][j - 1] == 'X' && a[i - 1][j + 1] == 'X'
     24 				&& a[i + 1][j - 1] == 'X' && a[i + 1][j + 1] == 'X'){
     25 				ans ++;	
     26 			}
     27 		}
     28 	}
     29 	printf("%d\n", ans);
     30 	return 0;
     31 }
     32 ```
     33 
     34 Tutorial is loading...
     35 
     36 **Code**
     37 
     38 ```
     39 #include <bits/stdc++.h>
     40 #define N 300010
     41 #define PII pair<int, int> 
     42 using namespace std;
     43 
     44 typedef long long LL;
     45 
     46 int n, m, a[N], c[N], t, d;
     47 LL ans = 0;
     48 
     49 priority_queue<PII, vector<PII>, greater<PII> > Q;
     50 
     51 int main(){
     52 	scanf("%d%d", &n, &m);
     53 	for (int i = 1; i <= n; i++){
     54 		scanf("%d", &a[i]);
     55 	}
     56 	
     57 	for (int i = 1; i <= n; i++){
     58 		scanf("%d", &c[i]);
     59 		Q.push(make_pair(c[i], i));
     60 	}
     61 	
     62 	for (int i = 1; i <= m; i++){
     63 		scanf("%d%d", &t, &d);
     64 		if (d <= a[t]){
     65 			a[t] -= d;
     66 			printf("%lld\n", 1LL * d * c[t]);
     67 		} else {
     68 			bool flag = false;
     69 			LL ans = 1LL * a[t] * c[t];
     70 			d -= a[t];
     71 			a[t] = 0;
     72 			while (!Q.empty()){
     73 				while (!Q.empty() && a[Q.top().second] == 0) Q.pop();
     74 				if (Q.empty()) break;
     75 				PII now = Q.top();
     76 				if (d <= a[now.second]){
     77 					a[now.second] -= d;
     78 					ans += 1LL * d * now.first;
     79 					flag = true;
     80 					printf("%lld\n", ans);
     81 					break;
     82 				} else {
     83 					ans += 1LL * a[now.second] * now.first;
     84 					d -= a[now.second];
     85 					a[now.second] = 0;
     86 					Q.pop();
     87 				}
     88 			}
     89 			
     90 			if (!flag){
     91 				puts("0");
     92 			}
     93 		}
     94 	}
     95 }
     96 ```
     97 
     98 Tutorial is loading...
     99 
    100 **Code**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 #define N 300010
    105 using namespace std;
    106 
    107 typedef long long LL;
    108 
    109 int n, a[N];
    110 LL ans = 0;
    111 
    112 int main(){
    113 	scanf("%d", &n);
    114 	for (int i = 1; i <= n; i++){
    115 		scanf("%d", &a[i]);
    116 	}
    117 	sort(a + 1, a + n + 1);
    118 	for (int i = 1; i <= n / 2; i++){
    119 		ans += 1LL * (a[i] + a[n - i + 1]) * (a[i] + a[n - i + 1]);
    120 	}
    121 	printf("%lld\n", ans);
    122 	return 0;
    123 }
    124 ```
    125 
    126 Tutorial is loading...
    127 
    128 **Code**
    129 
    130 ```
    131 #include <bits/stdc++.h>
    132 #define N 300010
    133 using namespace std;
    134 
    135 typedef long long LL;
    136 
    137 priority_queue<int, vector<int>, greater<int> > Q;
    138 vector<int> e[N];
    139 vector<int> seq;
    140 bool vis[N];
    141 int n, m;
    142 
    143 int main(){
    144 	scanf("%d%d", &n, &m);
    145 	for (int i = 1; i <= m; i++){
    146 		int u, v;
    147 		scanf("%d%d", &u, &v);
    148 		e[u].push_back(v);
    149 		e[v].push_back(u);
    150 	}
    151 	
    152 	vis[1] = true;
    153 	Q.push(1);
    154 	while (!Q.empty()){
    155 		int now = Q.top();
    156 		Q.pop();
    157 		seq.push_back(now);
    158 		for (auto p : e[now]){
    159 			if (!vis[p]){
    160 				Q.push(p);
    161 				vis[p] = true;
    162 			}
    163 		}
    164 	}
    165 	
    166 	for (auto p : seq){
    167 		printf("%d ", p);
    168 	}
    169 	puts("");
    170 	return 0;
    171 }
    172 ```
    173 
    174 Tutorial is loading...
    175 
    176 **Code**
    177 
    178 ```
    179 #include <bits/stdc++.h>
    180 #define N 100010
    181 using namespace std;
    182 
    183 typedef long long LL;
    184 
    185 struct Event{
    186 	int d, w, t;
    187 	
    188 	bool operator < (const Event &e) const {
    189 		return w > e.w || (w == e.w && d > e.d);
    190 	}
    191 };
    192 
    193 vector<Event> e[N];
    194 Event a[N];
    195 map<Event, int> cur;
    196 int n, m, k;
    197 
    198 LL f[2][N], ans = 0x3f3f3f3f3f3f3f3fLL;
    199 
    200 void insert(Event x){
    201 	if (cur.count(x)){
    202 		cur[x] ++;
    203 	} else {
    204 		cur[x] = 1;
    205 	}
    206 }
    207 
    208 void erase(Event x){
    209 	cur[x] --;
    210 	if (cur[x] == 0){
    211 		cur.erase(x);
    212 	}
    213 }
    214 
    215 int main(){
    216 	scanf("%d%d%d", &n, &m, &k);
    217 	for (int i = 1; i <= k; i++){
    218 		int s, t, d, w;
    219 		scanf("%d%d%d%d", &s, &t, &d, &w);
    220 		e[s].push_back((Event){d, w, 1});
    221 		e[t + 1].push_back((Event){d, w, -1});
    222 	}
    223 	
    224 	for (int i = 1; i <= n; i++){
    225 		for (auto p : e[i]){
    226 			if (p.t == 1){
    227 				insert(p);
    228 			} else {
    229 				erase(p);
    230 			}
    231 		}
    232 		
    233 		if (cur.size()){
    234 			a[i] = (*cur.begin()).first;
    235 		} else {
    236 			a[i] = (Event){i, 0, 0};
    237 		}
    238 	}
    239 	
    240 	memset(f, 0x3f, sizeof(f));
    241 	f[0][1] = 0;
    242 	for (int j = 0; j <= m; j++){
    243 		memset(f[(j ^ 1) & 1], 0x3f, sizeof(f[(j ^ 1) & 1]));
    244 		for (int i = 1; i <= n; i++){
    245 			f[(j ^ 1) & 1][i + 1] = min(f[(j ^ 1) & 1][i + 1], f[j & 1][i]);
    246 			f[j & 1][a[i].d + 1] = min(f[j & 1][a[i].d + 1], f[j & 1][i] + a[i].w);
    247 		}
    248 		ans = min(ans, f[j & 1][n + 1]);
    249 	}
    250 	printf("%lld\n", ans);
    251 	return 0;
    252 }
    253 ```
    254 
    255 Tutorial is loading...
    256 
    257 **Code**
    258 
    259 ```
    260 #include <bits/stdc++.h>
    261 #define N 210
    262 using namespace std;
    263 typedef long long LL;
    264 
    265 const LL p = 998244353;
    266 const LL g = 3;
    267 
    268 int k;
    269 LL n, m, b[N];
    270 
    271 struct Matrix{
    272 	int n;
    273 	LL mat[N][N];
    274 	
    275 	Matrix(){
    276 		n = 0;
    277 		memset(mat, 0, sizeof(mat));
    278 	}
    279 	
    280 	Matrix(int _n, LL diag){
    281 		n = _n;
    282 		memset(mat, 0, sizeof(mat));
    283 		for (int i = 1; i <= n; i++){
    284 			mat[i][i] = diag;
    285 		}
    286 	}
    287 	
    288 	Matrix(const Matrix &c){
    289 		n = c.n;
    290 		for (int i = 1; i <= n; i++){
    291 			for (int j = 1; j <= n; j++){
    292 				mat[i][j] = c.mat[i][j];
    293 			}
    294 		}
    295 	}
    296 	
    297 	Matrix operator * (const Matrix &a) const {
    298 		Matrix ans = Matrix(n, 0);
    299 		for (int k = 1; k <= n; k++){
    300 			for (int i = 1; i <= n; i++){
    301 				for (int j = 1; j <= n; j++){
    302 					ans.mat[i][j] += mat[i][k] * a.mat[k][j];
    303 					ans.mat[i][j] %= (p - 1);
    304 				}
    305 			}
    306 		}
    307 		return ans;
    308 	}
    309 	
    310 	Matrix mat_pow(LL t){
    311 		Matrix base = Matrix(*this), ans = Matrix(n, 1);
    312 		while (t){
    313 			if (t & 1){
    314 				ans = ans * base;
    315 			}
    316 			base = base * base;
    317 			t >>= 1;
    318 		}
    319 		return ans;
    320 	}
    321 
    322 };
    323 
    324 namespace GCD{
    325 	LL gcd(LL a, LL b){
    326 		if (!b) return a;
    327 		return gcd(b, a % b);
    328 	}
    329 	
    330 	LL ex_gcd(LL a, LL b, LL &x, LL &y){
    331 		if (!b){
    332 			x = 1; y = 0;
    333 			return a;
    334 		}
    335 		
    336 		LL q = ex_gcd(b, a % b, y, x);
    337 		y -= a / b * x;
    338 		return q;
    339 	}
    340 }
    341 
    342 namespace BSGS{
    343 	LL qpow(LL a, LL b, LL p){
    344 		LL ans = 1, base = a;
    345 		while (b){
    346 			if (b & 1){
    347 				(ans *= base) %= p;
    348 			}
    349 			(base *= base) %= p;
    350 			b >>= 1;
    351 		}
    352 		return ans;
    353 	}
    354 	
    355 	LL inv(LL x, LL p){
    356 		return qpow(x, p - 2, p);
    357 	}
    358 	
    359 	map<LL, LL> tab;
    360 	LL bsgs(LL a, LL b, LL p){
    361 		LL u = (LL) sqrt(p) + 1;
    362 		LL now = 1, step;
    363 		for (LL i = 0; i < u; i++){
    364 			LL tmp = b * inv(now, p) % p;
    365 			if (!tab.count(tmp)){
    366 				tab[tmp] = i;
    367 			}
    368 			(now *= a) %= p;
    369 		}
    370 		step = now;
    371 		now = 1;
    372 		for (LL i = 0; i < p; i += u){
    373 			if (tab.count(now)){
    374 				return i + tab[now];
    375 			}
    376 			(now *= step) %= p;
    377 		}
    378 		throw;
    379 		return -1;
    380 	}
    381 }
    382 
    383 namespace SOL{
    384 	LL solve(LL a, LL b, LL c){
    385 		if (c == 0) return 0;
    386 		LL q = GCD::gcd(a, b);
    387 		if (c % q){
    388 			return -1;
    389 		}
    390 		a /= q, b /= q, c /= q;
    391 		LL ans, _;
    392 		GCD::ex_gcd(a, b, ans, _);
    393 		(ans *= c) %= b;
    394 		while (ans < 0) ans += b;
    395 		return ans;
    396 	}
    397 }
    398 
    399 int main(){
    400 	scanf("%d", &k);
    401 	for (int i = 1; i <= k; i++){
    402 		scanf("%d", &b[i]);
    403 		b[i] %= (p - 1);
    404 	}
    405 	
    406 	scanf("%lld%lld", &n, &m);
    407 	
    408 	Matrix A = Matrix(k, 0);
    409 	for (int i = 1; i <= k; i++){
    410 		A.mat[1][i] = b[i];
    411 	}
    412 	
    413 	for (int i = 2; i <= k; i++){
    414 		A.mat[i][i - 1] = 1;
    415 	}
    416 	
    417 	A = A.mat_pow(n - k);
    418 	
    419 	LL ans = SOL::solve(A.mat[1][1], p - 1, BSGS::bsgs(g, m, p));
    420 	if (ans >= 0){
    421 		printf("%lld\n", BSGS::qpow(g, ans, p));
    422 	} else {
    423 		puts("-1");
    424 	}
    425 	return 0;
    426 }
    427 ```