codeforces-scrape

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

1030.md (18677B)


      1 Source: https://codeforces.com/blog/entry/62013
      2 
      3 [1030A - In Search of an Easy Problem](/contest/1030/problem/A "Technocup 2019 - Elimination Round 1")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include<bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 	int n; cin >> n;
     18 	
     19 	int curMax = 0;
     20 	for(int i = 0; i < n; i++) {
     21 		int curAns; cin >> curAns;
     22 		curMax = max(curMax, curAns);
     23 	}
     24 	puts(curMax > 0 ? "HARD" : "EASY");
     25 	return 0;
     26 }
     27 ```
     28 
     29 [1030B - Vasya and Cornfield](/contest/1030/problem/B "Technocup 2019 - Elimination Round 1")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution**
     36 
     37 ```
     38 #include<bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 int n, d;
     43 int m;
     44 
     45 int main() {
     46 	ios_base::sync_with_stdio(false);
     47     cin.tie(NULL);
     48 
     49 	cin >> n >> d;
     50 	cin >> m;
     51 	for(int i = 0; i < m; ++i){
     52 		int x, y;
     53 		cin >> x >> y;
     54 		
     55 		bool ok = true;
     56 		if(!((x - y) <= d && (x - y) >= -d)) 
     57 			ok = false;
     58 		if(!((x + y) <= n + n - d && (x + y) >= d))
     59 			ok = false;
     60 
     61 		if(ok) puts("YES");
     62 		else puts("NO");
     63 	}
     64 	return 0;
     65 }
     66 ```
     67 
     68 [1030C - Vasya and Golden Ticket](/contest/1030/problem/C "Technocup 2019 - Elimination Round 1")
     69 
     70 **Tutorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution**
     75 
     76 ```
     77 #include<bits/stdc++.h>
     78 
     79 using namespace std;
     80 
     81 int n;
     82 string s;
     83 
     84 int main() {
     85 	ios_base::sync_with_stdio(false);
     86     cin.tie(NULL);
     87 
     88 	cin >> n >> s;
     89 	int sum = 0;
     90 	for(int i = 0; i < n - 1; ++i){
     91 		sum += s[i] - '0';
     92 		
     93 		bool ok = true;
     94 		int pos = i + 1;
     95 		int sum2 = 0;
     96 		while(pos < n){
     97 			sum2 = s[pos++] - '0';
     98 			while(pos < n && sum2 + s[pos] - '0' <= sum){
     99 				sum2 += s[pos] - '0';
    100 				++pos;
    101 			}
    102 			if(sum2 != sum) ok = false;
    103 		}
    104 		
    105 		if(sum2 != sum) ok = false;
    106 		if(ok){
    107 			puts("YES");
    108 			return 0;
    109 		}
    110 	}
    111 	
    112 	puts("NO");	
    113 	return 0;
    114 }
    115 ```
    116 
    117 [1030D - Vasya and Triangle](/contest/1030/problem/D "Technocup 2019 - Elimination Round 1")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution**
    124 
    125 ```
    126 #include<bits/stdc++.h>
    127 
    128 using namespace std;
    129 
    130 long long gcd(long long a, long long b){
    131 	return a? gcd(b % a, a) : b;
    132 }
    133 
    134 int main() {
    135 	//freopen("input.txt", "r", stdin);
    136 	
    137     long long n, m, k;
    138     cin >> n >> m >> k;
    139     
    140     bool isEven = k % 2 == 0;
    141     long long p = n * m;
    142 	if(isEven) k /= 2;
    143 	
    144 	if(p % k != 0){
    145 		cout << "NO" << endl;
    146 		return 0;
    147 	}
    148 	
    149 	long long x = gcd(n, k);
    150 	k /= x;
    151 	long long a = n / x;
    152 		
    153 	x = gcd(m, k);
    154 	k /= x;
    155 	assert(k == 1);
    156 	long long b = m / x;
    157 		
    158 	
    159 	if(!isEven){
    160 		if(a < n)
    161 			a += a;
    162 		else{
    163 			assert(b < m);
    164 			b += b;
    165 		}
    166 	}
    167 	
    168 	cout << "YES" << endl;
    169 	cout << "0 0\n";
    170 	cout << 0 << ' ' << b << endl;
    171 	cout << a << ' ' << 0 << endl;
    172 	
    173 	return 0;
    174 }
    175 ```
    176 
    177 [1030E - Vasya and Good Sequences](/contest/1030/problem/E "Technocup 2019 - Elimination Round 1")
    178 
    179 **Tutorial**
    180 
    181 Tutorial is loading...
    182 
    183 **Solution**
    184 
    185 ```
    186 #include<bits/stdc++.h>
    187 
    188 using namespace std;
    189 
    190 const int N = int(3e5) + 9;
    191 
    192 int n;
    193 long long a[N];
    194 int b[N];
    195 int cnt[2][N];
    196 
    197 int main() {
    198 	ios_base::sync_with_stdio(false);
    199     cin.tie(NULL);
    200 
    201 	cin >> n;
    202 	for(int i = 0; i <n; ++i){
    203 		cin >> a[i];
    204 		b[i] = __builtin_popcountll(a[i]);	
    205 	}
    206 	
    207 	long long res = 0;
    208 	int sufSum = 0;
    209 	cnt[0][n] = 1;
    210 	for(int i = n - 1; i >= 0; --i){
    211 		int sum = 0, mx = 0;
    212 		int lstJ = i;
    213 		int add = 0;
    214 		for(int j = i; j < n && j - i < 65; ++j){
    215 			sum += b[j];
    216 			mx = max(mx, b[j]);
    217 			if(mx > sum - mx && sum % 2 == 0) --add;
    218 			lstJ = j;
    219 		}		
    220 		
    221 		sufSum += b[i];
    222 		add += cnt[sufSum & 1][i + 1];
    223 		res += add;	
    224 		
    225 		cnt[0][i] = cnt[0][i + 1];
    226 		cnt[1][i] = cnt[1][i + 1];
    227 		if(sufSum & 1) ++cnt[1][i];
    228 		else ++cnt[0][i];
    229 	}
    230 	
    231 	cout << res << endl;
    232 	return 0;
    233 }
    234 ```
    235 
    236 [1030F - Putting Boxes Together](/contest/1030/problem/F "Technocup 2019 - Elimination Round 1")
    237 
    238 **Tutorial**
    239 
    240 Tutorial is loading...
    241 
    242 **Fenwick Solution**
    243 
    244 ```
    245 #include<bits/stdc++.h>
    246 
    247 using namespace std;
    248 
    249 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    250 typedef long long li;
    251 
    252 const int MOD = int(1e9) + 7;
    253 
    254 int norm(int a) {
    255 	if(a >= MOD)
    256 		a -= MOD;
    257 	if(a < 0)
    258 		a += MOD;
    259 	return a;
    260 }
    261 
    262 int norm(const li &a) {
    263 	return norm(int(a % MOD));
    264 }
    265 
    266 int mul(int a, int b) {
    267 	return int((a * 1ll * b) % MOD);
    268 }
    269 
    270 const int N = 200 * 1000 + 555;
    271 
    272 int n, q;
    273 int a[N], w[N];
    274 
    275 inline bool read() {
    276 	if(!(cin >> n >> q))
    277 		return false;
    278 	fore(i, 0, n)
    279 		assert(scanf("%d", &a[i]) == 1);
    280 	fore(i, 0, n)
    281 		assert(scanf("%d", &w[i]) == 1);
    282 	return true;
    283 }
    284 
    285 li fW[N], fAW[N];
    286 
    287 void inc(li f[N], int pos, li val) {
    288 	for(; pos < N; pos |= pos + 1)
    289 		f[pos] += val;
    290 }
    291 
    292 li sum(li f[N], int pos) {
    293 	li ans = 0;
    294 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    295 		ans += f[pos];
    296 	return ans;
    297 }
    298 
    299 li getSum(li f[N], int l, int r) {
    300 	return sum(f, r - 1) - sum(f, l - 1);
    301 }
    302 
    303 int getNSum(li f[N], int l, int r) {
    304 	return norm(sum(f, r - 1) - sum(f, l - 1));
    305 }
    306 
    307 inline void solve() {
    308 	fore(i, 0, n) {
    309 		a[i] -= i;
    310 		inc(fW, i, w[i]);
    311 		inc(fAW, i, mul(a[i], w[i]));
    312 	}
    313 	
    314 	fore(_, 0, q) {
    315 		int x, y;
    316 		assert(scanf("%d%d", &x, &y) == 2);
    317 		if(x < 0) {
    318 			x = -x - 1;
    319 			inc(fW, x, -w[x]);
    320 			inc(fAW, x, -mul(a[x], w[x]));
    321 			
    322 			w[x] = y;
    323 			inc(fW, x, w[x]);
    324 			inc(fAW, x, mul(a[x], w[x]));
    325 		} else {
    326 			x--;
    327 			li sum = getSum(fW, x, y);
    328 			
    329 			int lf = x, rg = y;
    330 			while(rg - lf > 1) {
    331 				int mid = (lf + rg) >> 1;
    332 				if(2 * getSum(fW, x, mid) > sum)
    333 					rg = mid;
    334 				else
    335 					lf = mid;
    336 			}
    337 			assert(x <= lf && lf < y);
    338 			
    339 			int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf));
    340 			ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) );
    341 			printf("%d\n", ans);
    342 		}
    343 	}
    344 }
    345 
    346 int main() {
    347 #ifdef _DEBUG
    348 	freopen("input.txt", "r", stdin);
    349 	int tt = clock();
    350 #endif
    351 	cout << fixed << setprecision(15);
    352 	
    353 	if(read()) {
    354 		solve();
    355 		
    356 #ifdef _DEBUG
    357 		cerr << "TIME = " << clock() - tt << endl;
    358 		tt = clock();
    359 #endif
    360 	}
    361 	return 0;
    362 }
    363 ```
    364 
    365 **Segment Tree Solution**
    366 
    367 ```
    368 #include<bits/stdc++.h>
    369 
    370 using namespace std;
    371 
    372 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    373 #define sz(a) int((a).size())
    374 
    375 #define x first
    376 #define y second
    377 
    378 typedef long long li;
    379 
    380 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    381 	return out << "(" << p.x << ", " << p.y << ")";
    382 }
    383 
    384 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    385 	out << "[";
    386 	fore(i, 1, int(v.size())) {
    387 		if(i) out << ", ";
    388 		out << v[i];
    389 	}
    390 	return out << "]";
    391 }
    392 
    393 const int INF = int(1e9);
    394 const li INF64 = li(1e18);
    395 
    396 const int MOD = int(1e9) + 7;
    397 
    398 int norm(int a) {
    399 	while(a >= MOD)
    400 		a -= MOD;
    401 	while(a < 0)
    402 		a += MOD;
    403 	return a;
    404 }
    405 
    406 int norm(const li &a) {
    407 	return norm(int(a % MOD));
    408 }
    409 
    410 int mul(int a, int b) {
    411 	return int((a * 1ll * b) % MOD);
    412 }
    413 
    414 const int N = 300 * 1000 + 555;
    415 
    416 int n, q;
    417 int a[N], w[N];
    418 
    419 inline bool read() {
    420 	if(!(cin >> n >> q))
    421 		return false;
    422 	fore(i, 0, n)
    423 		assert(scanf("%d", &a[i]) == 1);
    424 	fore(i, 0, n)
    425 		assert(scanf("%d", &w[i]) == 1);
    426 	return true;
    427 }
    428 
    429 li TW[4 * N], TAW[4 * N];
    430 
    431 void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) {
    432 	if(l + 1 == r) {
    433 		assert(l == pos);
    434 		T[v] += val;
    435 		return;
    436 	}
    437 	int mid = (l + r) >> 1;
    438 	if(pos < mid)
    439 		addVAl(T, 2 * v + 1, l, mid, pos, val);
    440 	else
    441 		addVAl(T, 2 * v + 2, mid, r, pos, val);
    442 	T[v] = T[2 * v + 1] + T[2 * v + 2];
    443 }
    444 
    445 li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) {
    446 	if(l == lf && r == rg)
    447 		return T[v];
    448 	int mid = (l + r) >> 1;
    449 	li ans = 0;
    450 	if(lf < mid)
    451 		ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg));
    452 	if(rg > mid)
    453 		ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg);
    454 	return ans;
    455 }
    456 
    457 int getNSum(li T[4 * N], int l, int r) {
    458 	if(l >= r) return 0;
    459 	return int(getSum(T, 0, 0, n, l, r) % MOD);
    460 }
    461 
    462 pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) {
    463 	if(l == lf && r == rg) {
    464 		if(TW[v] <= val)
    465 			return make_pair(INF, TW[v]);
    466 		if(l + 1 == r)
    467 			return make_pair(l, 0);
    468 	}
    469 	int mid = (l + r) >> 1;
    470 	
    471 	int res = INF;
    472 	li sum = 0;
    473 	if(lf < mid) {
    474 		auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val);
    475 		res = min(res, cur.x);
    476 		sum += cur.y;
    477 	}
    478 	if(rg > mid && res == INF) {
    479 		auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum);
    480 		res = min(res, cur.x);
    481 		sum += cur.y;
    482 	}
    483 	return make_pair(res, sum);
    484 }
    485 
    486 inline void solve() {
    487 	fore(i, 0, n) {
    488 		a[i] -= i;
    489 		addVAl(TW, 0, 0, n, i, w[i]);
    490 		addVAl(TAW, 0, 0, n, i, mul(a[i], w[i]));
    491 	}
    492 	
    493 	fore(_, 0, q) {
    494 		int x, y;
    495 		assert(scanf("%d%d", &x, &y) == 2);
    496 		if(x < 0) {
    497 			x = -x - 1;
    498 			addVAl(TW, 0, 0, n, x, -w[x]);
    499 			addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x]));
    500 			
    501 			w[x] = y;
    502 			addVAl(TW, 0, 0, n, x, w[x]);
    503 			addVAl(TAW, 0, 0, n, x, mul(a[x], w[x]));
    504 		} else {
    505 			x--;
    506 			li sum = getSum(TW, 0, 0, n, x, y);
    507 			int pos = getPos(0, 0, n, x, y, sum / 2).x;
    508 			assert(x <= pos && pos < y);
    509 			
    510 			int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos));
    511 			ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) );
    512 			printf("%d\n", ans);
    513 		}
    514 	}
    515 }
    516 
    517 int main() {
    518 #ifdef _DEBUG
    519 	freopen("input.txt", "r", stdin);
    520 	int tt = clock();
    521 #endif
    522 	cout << fixed << setprecision(15);
    523 	
    524 	if(read()) {
    525 		solve();
    526 		
    527 #ifdef _DEBUG
    528 		cerr << "TIME = " << clock() - tt << endl;
    529 		tt = clock();
    530 #endif
    531 	}
    532 	return 0;
    533 }
    534 ```
    535 
    536 [1030G - Linear Congruential Generator](/contest/1030/problem/G "Technocup 2019 - Elimination Round 1")
    537 
    538 **Tutorial**
    539 
    540 Tutorial is loading...
    541 
    542 **Dynamic Connectivity Solution**
    543 
    544 ```
    545 #include<bits/stdc++.h>
    546 
    547 using namespace std;
    548 
    549 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    550 #define sz(a) int((a).size())
    551 
    552 #define x first
    553 #define y second
    554 
    555 typedef long long li;
    556 typedef pair<int, int> pt;
    557 
    558 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    559 	return out << "(" << p.x << ", " << p.y << ")";
    560 }
    561 
    562 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    563 	out << "[";
    564 	fore(i, 0, sz(v)) {
    565 		if(i) out << ", ";
    566 		out << v[i];
    567 	}
    568 	return out << "]";
    569 }
    570 
    571 const int MOD = int(1e9) + 7;
    572 
    573 int mul(int a, int b) {
    574 	return int(a * 1ll * b % MOD);
    575 }
    576 
    577 int binPow(int a, int k) {
    578 	int ans = 1;
    579 	while(k > 0) {
    580 		if(k & 1) ans = mul(ans, a);
    581 		a = mul(a, a);
    582 		k >>= 1;
    583 	}
    584 	return ans;
    585 }
    586 
    587 const int M = 2000 * 1000 + 555;
    588 const int N = 200 * 1000 + 555;
    589 
    590 int n, p[N];
    591 
    592 inline bool read() {
    593 	if(!(cin >> n))
    594 		return false;
    595 	fore(i, 0, n)
    596 		assert(scanf("%d", &p[i]) == 1);
    597 	return true;
    598 }
    599 
    600 int minD[M];
    601 vector<pt> ps[M];
    602 
    603 void precalc() {
    604 	iota(minD, minD + M, 0);
    605 	fore(i, 2, M) {
    606 		if(minD[i] < i)
    607 			continue;
    608 		
    609 		for(li j = i * 1ll * i; j < M; j += i)
    610 			minD[j] = min(minD[j], i);
    611 	}
    612 	
    613 	fore(i, 2, M) {
    614 		int v = i;
    615 		ps[i].clear();
    616 		
    617 		while(v > 1) {
    618 			int md = minD[v];
    619 			if(ps[i].empty() || ps[i].back().x != md)
    620 				ps[i].emplace_back(md, 0);
    621 			ps[i].back().y++;
    622 			v /= md;
    623 		}
    624 	}
    625 }
    626 
    627 int baseA[M], cntNotZero = 0;
    628 
    629 int a[M];
    630 int mark[M];
    631 
    632 void insert(int v) {
    633 	if(a[v] < 1) {
    634 		a[v] = 1;
    635 		mark[v] = 1;
    636 		return;
    637 	}
    638 	for(auto p : ps[v - 1]) {
    639 		a[p.x] = max(a[p.x], p.y);
    640 		if(mark[p.x]) {
    641 			mark[p.x] = 0;
    642 			insert(p.x);
    643 		}
    644 	}
    645 }
    646 
    647 vector<int*> pnt;
    648 vector<int> val;
    649 
    650 void upd(int &pos, int nval) {
    651 	pnt.push_back(&pos);
    652 	val.push_back(pos);
    653 	
    654 	pos = nval;
    655 }
    656 
    657 void roll_back() {
    658 	*(pnt.back()) = val.back();
    659 	pnt.pop_back();
    660 	val.pop_back();
    661 }
    662 
    663 bool ok[N];
    664 int cntSame = 0;
    665 vector<int> Top[4 * N];
    666 
    667 void addOp(int v, int l, int r, int lf, int rg, int val) {
    668 	if(l == lf && r == rg) {
    669 		Top[v].push_back(val);
    670 		return;
    671 	}
    672 	int mid = (l + r) >> 1;
    673 	if(lf < mid)
    674 		addOp(2 * v + 1, l, mid, lf, min(mid, rg), val);
    675 	if(rg > mid)
    676 		addOp(2 * v + 2, mid, r, max(lf, mid), rg, val);
    677 }
    678 
    679 void insertDC(int v) {
    680 	if(a[v] < 1) {
    681 		upd(a[v], 1);
    682 		upd(mark[v], 1);
    683 		if(a[v] == baseA[v])
    684 			upd(cntSame, cntSame + 1);
    685 		return;
    686 	}
    687 	for(auto p : ps[v - 1]) {
    688 		if(a[p.x] < p.y) {
    689 			upd(a[p.x], p.y);
    690 			if(a[p.x] == baseA[p.x])
    691 				upd(cntSame, cntSame + 1);
    692 		}
    693 		if(mark[p.x]) {
    694 			upd(mark[p.x], 0);
    695 			insertDC(p.x);
    696 		}
    697 	}
    698 }
    699 
    700 void calcAns(int v, int l, int r) {
    701 	int curOp = sz(pnt);
    702 	for(int cv : Top[v])
    703 		insertDC(cv);
    704 	
    705 	if(l + 1 == r) {
    706 		ok[l] = cntSame == cntNotZero;
    707 	} else {
    708 		int mid = (l + r) >> 1;
    709 		calcAns(2 * v + 1, l, mid);
    710 		calcAns(2 * v + 2, mid, r);
    711 	}
    712 	while(sz(pnt) > curOp)
    713 		roll_back();
    714 }
    715 
    716 inline void solve() {
    717 	memset(baseA, 0, sizeof baseA);
    718 	memset(a, 0, sizeof a);
    719 	memset(mark, 0, sizeof mark);
    720 	
    721 	fore(i, 0, n)
    722 		insert(p[i]);
    723 		
    724 	cntNotZero = 0;
    725 	fore(i, 0, M) {
    726 		baseA[i] = a[i];
    727 		cntNotZero += a[i] > 0;
    728 	}
    729 	
    730 	memset(a, 0, sizeof a);
    731 	memset(mark, 0, sizeof mark);
    732 	fore(i, 0, n) {
    733 		if(i > 0)
    734 			addOp(0, 0, n, 0, i, p[i]);
    735 		if(i + 1 < n)
    736 			addOp(0, 0, n, i + 1, n, p[i]);
    737 	}
    738 	calcAns(0, 0, n);
    739 	
    740 	int lcm = 1;
    741 	fore(i, 1, M)
    742 		lcm = mul(lcm, binPow(i, baseA[i]));
    743 	int add = 0;
    744 	fore(i, 0, n)
    745 		if(ok[i])
    746 			add = 1;
    747 	cout << (lcm + add) % MOD << endl;
    748 }
    749 
    750 int main() {
    751 #ifdef _DEBUG
    752 	freopen("input.txt", "r", stdin);
    753 	int tt = clock();
    754 #endif
    755 	cout << fixed << setprecision(15);
    756 	
    757 	precalc();
    758 	if(read()) {
    759 		solve();
    760 		
    761 #ifdef _DEBUG
    762 		cerr << "TIME = " << clock() - tt << endl;
    763 		tt = clock();
    764 #endif
    765 	}
    766 	return 0;
    767 }
    768 ```
    769 
    770 **Greedy Solution**
    771 
    772 ```
    773 #include<bits/stdc++.h>
    774 
    775 using namespace std;
    776 
    777 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    778 #define sz(a) int((a).size())
    779 
    780 #define x first
    781 #define y second
    782 
    783 typedef long long li;
    784 typedef pair<int, int> pt;
    785 
    786 const int MOD = int(1e9) + 7;
    787 
    788 int mul(int a, int b) {
    789 	return int(a * 1ll * b % MOD);
    790 }
    791 
    792 int binPow(int a, int k) {
    793 	int ans = 1;
    794 	while(k > 0) {
    795 		if(k & 1) ans = mul(ans, a);
    796 		a = mul(a, a);
    797 		k >>= 1;
    798 	}
    799 	return ans;
    800 }
    801 
    802 const int M = 2000 * 1000 + 555;
    803 
    804 int minD[M];
    805 vector<pt> ps[M];
    806 
    807 inline void precalc() {
    808 	iota(minD, minD + M, 0);
    809 	
    810 	fore(val, 2, M) {
    811 		if(minD[val] < val)
    812 			continue;
    813 			
    814 		for(li j = val * 1ll * val; j < M; j += val)
    815 			minD[j] = min(minD[j], val);
    816 	}
    817 	
    818 	fore(i, 2, M) {
    819 		int v = i;
    820 		ps[i].clear();
    821 		
    822 		while(v > 1) {
    823 			int md = minD[v];
    824 			if(ps[i].empty() || ps[i].back().x != md)
    825 				ps[i].emplace_back(md, 0);
    826 			ps[i].back().y++;
    827 			v /= md;
    828 		}
    829 	}
    830 }
    831 
    832 int n;
    833 vector<int> p;
    834 
    835 inline bool read() {
    836 	if(!(cin >> n))
    837 		return false;
    838 	p.assign(n, 0);
    839 	fore(i, 0, n)
    840 		assert(scanf("%d", &p[i]) == 1);
    841 	return true;
    842 }
    843 
    844 int a[M], cnt[M];
    845 
    846 inline void solve() {
    847 	sort(p.begin(), p.end(), greater<int>());
    848 	
    849 	for(int& cp : p) {
    850 		if(a[cp] == 0) {
    851 			a[cp] = 1;
    852 			cnt[cp] = 1;
    853 		} else {
    854 			cp--;
    855 			for(auto np : ps[cp]) {
    856 				if(a[np.x] < np.y) {
    857 					a[np.x] = np.y;
    858 					cnt[np.x] = 1;
    859 				} else if(a[np.x] == np.y)
    860 					cnt[np.x]++;
    861 			}
    862 		}
    863 	}
    864 	
    865 	int add = 0;
    866 	for(int cp : p) {
    867 		bool un = false;
    868 		for(auto np : ps[cp])
    869 			un |= (a[np.x] == np.y && cnt[np.x] == 1);
    870 		if(!un)
    871 			add = 1;
    872 	}
    873 	
    874 	int lcm = 1;
    875 	fore(i, 2, M)
    876 		lcm = mul(lcm, binPow(i, a[i]));
    877 	cout << (lcm + add) % MOD << endl;
    878 }
    879 
    880 int main(){
    881 #ifdef _DEBUG
    882 	freopen("input.txt", "r", stdin);
    883 	int t = clock();
    884 #endif
    885 	cout << fixed << setprecision(10);
    886 
    887 	precalc();
    888 	if(read()) {
    889 		solve();	
    890 		
    891 #ifdef _DEBUG
    892 		cerr << "TIME = " << clock() - t << endl;
    893 #endif
    894 	}
    895 	return 0;
    896 }
    897 ```
    898 
    899 [1053E - Euler tour](/contest/1053/problem/E "Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1)")
    900 
    901 **Tutorial**
    902 
    903 Tutorial is loading...
    904 
    905 **Solution**
    906 
    907 ```
    908 #include <bits/stdc++.h>
    909 
    910 using namespace std;
    911 
    912 #define st first
    913 #define nd second
    914 #define PII pair <int, int>
    915 
    916 const int N = 1e6 + 7;
    917 
    918 int n;
    919 int in[N];
    920 int ans[N];
    921 bool used[N];
    922 vector <int> unused;
    923 
    924 int cnt;
    925 deque <PII> cur;
    926 vector <PII> getEqual;
    927 
    928 set <int> S;
    929 vector <int> place[N];
    930 vector <pair <int, int> > order;
    931 
    932 bool check(){
    933 	if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1])
    934 		return false;
    935 	
    936 	for(int i = 1; i + 1 < n + n; ++i)
    937 		if(in[i] == in[i + 1] && in[i] != 0)
    938 			return false;
    939 	
    940 	for(int i = 1; i < n + n; ++i){
    941 		if(in[i] == 0)
    942 			continue;
    943 
    944 		if(place[in[i]].size() == 0)
    945 			order.push_back({i, in[i]});
    946 		place[in[i]].push_back(i);
    947 	}
    948 	
    949 	for(int i = 1; i <= n; ++i)
    950 		for(int j = 1; j < place[i].size(); ++j)
    951 			if(place[i][j]%2 != place[i][j - 1]%2)
    952 				return false;
    953 	
    954 	S.insert(n + n);
    955 	sort(order.begin(), order.end());
    956 	
    957 	for(auto v: order){
    958 		auto it = S.lower_bound(v.first);
    959 		if(*it < place[v.second].back())
    960 			return false;
    961 		
    962 		for(int c: place[v.second])
    963 			S.insert(c);
    964 	}
    965 	
    966 	return true;
    967 }
    968 
    969 inline int get(){
    970     if(unused.size() == 0){
    971         puts("no");
    972         exit(0);
    973     }
    974 
    975 	int ret = unused.back();
    976 	unused.pop_back();
    977 	return ret;
    978 }
    979 
    980 void go(){
    981 	deque <PII> help;
    982 	while(help.size() + cur.size() >= 3){
    983 		if(help.size() < 3){
    984 			help.push_back(cur.front());
    985 			cur.pop_front();
    986 			continue;
    987 		}
    988 		
    989 		PII v1 = help.back(); help.pop_back();
    990 		PII v2 = help.back(); help.pop_back();
    991 		PII v3 = help.back(); help.pop_back();
    992 		
    993 		if(v1.st == 0 && v2.st != 0 && v3.st != 0){
    994 			ans[v1.nd] = v3.st;
    995 			help.push_back(v3);
    996 		}
    997 		else{
    998 			help.push_back(v3);
    999 			help.push_back(v2);
   1000 			help.push_back(v1);
   1001 		}
   1002 		
   1003 		if(cur.size() == 0)
   1004 			break;
   1005 		
   1006 		help.push_back(cur.front());
   1007 		cur.pop_front();
   1008 	}
   1009 	
   1010 	while(help.size()){
   1011 		cur.push_back(help.front());
   1012 		help.pop_front();
   1013 	}
   1014 }
   1015 
   1016 void solve(int root){
   1017 	int need = (cur.size() + 1) / 2 - cnt;
   1018 	if(need < 0){
   1019 	    puts("no");
   1020 	    exit(0);
   1021 	}
   1022 	deque <PII> help;
   1023 	
   1024 	while(cur.size()){
   1025 		auto v = cur.front();
   1026 		cur.pop_front();
   1027 
   1028 		if(need > 0 && v.st == 0){
   1029 			--need;
   1030 			v.st = get();
   1031 			ans[v.nd] = v.st;
   1032 		}
   1033 		
   1034 		help.push_back(v);
   1035 	}
   1036 	
   1037 	while(help.size()){
   1038 		cur.push_front(help.front());
   1039 		help.pop_front();
   1040 	}
   1041 
   1042 	go();
   1043 	if(root == -1 && cur.back().st == 0){
   1044 		root = cur.front().st;
   1045 		ans[cur.back().nd] = root;
   1046 
   1047 		cur.pop_front();
   1048 		cur.pop_back();
   1049 		solve(root);
   1050 		return;
   1051 	}
   1052 	
   1053 	reverse(cur.begin(), cur.end());
   1054 	go();
   1055 	
   1056 	while(cur.size() > 0){
   1057 		auto v = cur.front();
   1058 		cur.pop_front();
   1059 		
   1060 		if(v.st == 0)
   1061 			ans[v.nd] = root;
   1062 	}
   1063 	
   1064 }
   1065 
   1066 int main(){
   1067 	scanf("%d", &n);
   1068 	for(int i = 1; i < n + n; ++i){
   1069 		scanf("%d", &in[i]);
   1070 		used[in[i]] = true;
   1071 	}
   1072 	
   1073 	if(!check()){
   1074 		puts("no");
   1075 		return 0;
   1076 	}
   1077 	
   1078 	if(in[1] != 0)
   1079 		in[n + n - 1] = in[1];
   1080 	else if(in[n + n - 1] != 0)
   1081 		in[1] = in[n + n - 1];
   1082 	
   1083 	for(int i = 1; i <= n; ++i){
   1084 		if(!used[i])
   1085 			unused.push_back(i);
   1086 		used[i] = false;
   1087 	}
   1088 	
   1089 	for(int i = 1; i < n + n; ++i)
   1090 		ans[i] = in[i];
   1091 	
   1092 	for(int i = 1; i < n + n; ++i){
   1093 		if(in[i] == 0){
   1094 			getEqual.push_back({in[i], i});
   1095 			continue;
   1096 		}
   1097 
   1098 		if(used[in[i]]){
   1099 			cnt = 0;
   1100 			while(getEqual.back().st != in[i]){
   1101 				if(getEqual.back().st > 0){
   1102 					++cnt;
   1103 					used[getEqual.back().st] = false;
   1104 				}
   1105 
   1106 				cur.push_front(getEqual.back());
   1107 				getEqual.pop_back();
   1108 			}
   1109 			
   1110 			solve(in[i]);
   1111 			continue;
   1112 		}
   1113 		
   1114 		getEqual.push_back({in[i], i});
   1115 		used[in[i]] = true;
   1116 	}
   1117 	
   1118 	cnt = 0;
   1119 	while(getEqual.size()){
   1120 		if(getEqual.back().st > 0){
   1121 			++cnt;
   1122 			used[getEqual.back().st] = false;
   1123 		}
   1124 
   1125 		cur.push_front(getEqual.back());
   1126 		getEqual.pop_back();
   1127 	}
   1128 	
   1129 	solve(-1);
   1130 	puts("yes");
   1131 	for(int i = 1; i < n + n; ++i)
   1132 		printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' ');
   1133 	return 0;
   1134 }
   1135 ```