codeforces-scrape

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

2062.md (18451B)


      1 Source: https://codeforces.com/blog/entry/138866
      2 
      3 [2062A - String](/contest/2062/problem/A)
      4 
      5 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk").
      6 
      7 **Rate this problem**
      8 
      9 Good problem
     10 
     11 Average problem
     12 
     13 Bad problem
     14 
     15 Did not solve
     16 
     17 **Solution**
     18 
     19 Tutorial is loading...
     20 
     21 **Code (C++)**
     22 
     23 ```
     24 #include<bits/stdc++.h>
     25 using namespace std;
     26 string s;
     27 int main(){
     28 	ios::sync_with_stdio(false),cin.tie(0);
     29 	int T,n,i,ans;
     30 	for(cin>>T;T>0;T--)
     31 	{
     32 		cin>>s;n=s.size();
     33 		ans=0;
     34 		for(i=0;i<n;i++)ans+=s[i]-'0';
     35 		cout<<ans<<'\n';
     36 	}
     37 	return 0;
     38 }
     39 ```
     40 
     41 **Code (Python)**
     42 
     43 ```
     44 for _ in range(int(input())):
     45     print(input().count('1'))
     46 ```
     47 
     48 [2062B - Clockwork](/contest/2062/problem/B)
     49 
     50 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk").
     51 
     52 **Rate this problem**
     53 
     54 Good problem
     55 
     56 Average problem
     57 
     58 Bad problem
     59 
     60 Did not solve
     61 
     62 **Solution**
     63 
     64 Tutorial is loading...
     65 
     66 **Code (C++)**
     67 
     68 ```
     69 #include<bits/stdc++.h>
     70 using namespace std;
     71 int main(){
     72 	ios::sync_with_stdio(false),cin.tie(0);
     73 	int T,n,i,t,flag;
     74 	for(cin>>T;T>0;T--)
     75 	{
     76 		cin>>n;
     77 		flag=0;
     78 		for(i=0;i<n;i++)
     79 		{
     80 			cin>>t;
     81 			if(t<=i*2||t<=(n-i-1)*2)flag=1;
     82 		}
     83 		if(flag)cout<<"NO\n";
     84 		else cout<<"YES\n";
     85 	}
     86 	return 0;
     87 }
     88 ```
     89 
     90 **Code (Python)**
     91 
     92 ```
     93 for _ in range(int(input())):
     94     n=int(input())
     95     a=list(map(int,input().split()))
     96     for i in range(n):
     97         if a[i]<=max(i,n-i-1)*2:
     98             print('NO')
     99             break
    100     else:
    101         print('YES')
    102 ```
    103 
    104 [2062C - Cirno and Operations](/contest/2062/problem/C)
    105 
    106 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Preparation: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [mejiamejia](/profile/mejiamejia "Expert mejiamejia").
    107 
    108 **Rate this problem**
    109 
    110 Good problem
    111 
    112 Average problem
    113 
    114 Bad problem
    115 
    116 Did not solve
    117 
    118 **Solution**
    119 
    120 Tutorial is loading...
    121 
    122 **Code (C++)**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126 using namespace std;
    127  
    128 long long a[1010];
    129  
    130 int main(){
    131 	int t;
    132 	cin >> t;
    133 	while (t--){
    134 		int n;
    135 		cin >> n;
    136 		for (int i = 1; i <= n; i++) cin >> a[i];
    137 		int now = n;
    138 		long long ans = -1e18;
    139 		for (int i = 1; i <= n; i++){
    140 			long long sum = 0;
    141 			for (int i = 1; i <= now; i++) sum = (sum + a[i]) ;
    142 			if (i == 1) ans = max(ans, sum);
    143 			else ans = max(ans, max(sum, ( - sum) ));
    144 			for (int i = 1; i < now; i++) a[i] = (a[i + 1] - a[i]) ;
    145 			now--;
    146 		}
    147 		cout << ans << endl; 
    148 	}
    149 	return 0;
    150 }
    151 ```
    152 
    153 **Code (Python)**
    154 
    155 ```
    156 from math import *
    157 for _ in range(int(input())):
    158 	n=int(input())
    159 	a=list(map(int,input().split()))
    160 	ans=sum(a)
    161 	while n>1:
    162 		n-=1
    163 		a=[a[i+1]-a[i] for i in range(n)]
    164 		ans=max(ans,abs(sum(a)))
    165 	print(ans)
    166 ```
    167 
    168 [2062D - Balanced Tree](/contest/2062/problem/D)
    169 
    170 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs").
    171 
    172 **Rate this problem**
    173 
    174 Good problem
    175 
    176 Average problem
    177 
    178 Bad problem
    179 
    180 Did not solve
    181 
    182 **Solution**
    183 
    184 Tutorial is loading...
    185 
    186 **Code (C++)**
    187 
    188 ```
    189 #include "bits/stdc++.h"
    190 using namespace std;
    191 #define all(x) (x).begin(),(x).end()
    192 int main()
    193 {
    194 	ios::sync_with_stdio(0); cin.tie(0);
    195 	int T; cin >> T;
    196 	while (T--)
    197 	{
    198 		int n, i;
    199 		cin >> n;
    200 		vector<int> l(n), r(n), a(n);
    201 		for (i = 0; i < n; i++) cin >> l[i] >> r[i];
    202 		vector e(n, vector<int>(0));
    203 		for (i = 1; i < n; i++)
    204 		{
    205 			int u, v;
    206 			cin >> u >> v;
    207 			--u, --v;
    208 			e[u].push_back(v);
    209 			e[v].push_back(u);
    210 		}
    211 		long long ans = 0;
    212 		function<void(int)> dfs = [&](int u) {
    213 			int mx = l[u];
    214 			for (int v : e[u])
    215 			{
    216 				erase(e[v], u);
    217 				dfs(v);
    218 				mx = max(mx, a[v]);
    219 			}
    220 			a[u] = min(mx, r[u]);
    221 			for (int v : e[u]) ans += max(0, a[v] - a[u]);
    222 		};
    223 		dfs(0);
    224 		cout << ans + a[0] << "\n";
    225 	}
    226 }
    227 ```
    228 
    229 **Code (Python)**
    230 
    231 ```
    232 for _ in range(int(input())):
    233 	n = int(input())
    234 	l,r=[],[]
    235 	for i in range(n):
    236 		L,R=map(int,input().split())
    237 		l.append(L)
    238 		r.append(R)
    239 	e=[[] for i in range(n)]
    240 	for i in range(n-1):
    241 		u,v=map(int,input().split())
    242 		e[u-1].append(v-1)
    243 		e[v-1].append(u-1)
    244 	stk=[0]
    245 	f=[-1]*n
    246 	nfd=[]
    247 	while stk:
    248 		u=stk.pop()
    249 		nfd.append(u)
    250 		for v in e[u]:
    251 			if v!=f[u]:
    252 				f[v]=u
    253 				stk.append(v)
    254 	nfd.reverse()
    255 	ans=0
    256 	for u in nfd:
    257 		for v in e[u]:
    258 			if f[v]==u:
    259 				l[u]=max(l[u],l[v])
    260 		l[u]=min(l[u],r[u])
    261 		for v in e[u]:
    262 			if f[v]==u:
    263 				ans+=max(0,l[v]-l[u])
    264 	print(ans+l[0])
    265 ```
    266 
    267 [2062E1 - The Game (Easy Version)](/contest/2062/problem/E1)
    268 
    269 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Preparation: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"),[mejiamejia](/profile/mejiamejia "Expert mejiamejia"),[SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs").
    270 
    271 **Rate this problem**
    272 
    273 Good problem
    274 
    275 Average problem
    276 
    277 Bad problem
    278 
    279 Did not solve
    280 
    281 **Solution**
    282 
    283 Tutorial is loading...
    284 
    285 **Code (C++)**
    286 
    287 ```
    288 #include "bits/stdc++.h"
    289 using namespace std;
    290 const int N=1e6+5;
    291 vector<int> e[N];
    292 int w[N],dfn[N],nfd[N],pre[N],suf[N],low[N];
    293 bool ed[N];
    294 int id;
    295 void dfs(int u)
    296 {
    297 	if (ed[u]) return;
    298 	ed[u]=1;
    299 	dfn[u]=++id;
    300 	nfd[id]=u;
    301 	for (int v:e[u]) dfs(v);
    302 	ed[u]=0;
    303 	low[u]=id;
    304 }
    305 int main()
    306 {
    307 	ios::sync_with_stdio(0); cin.tie(0);
    308 	cout<<fixed<<setprecision(15);
    309 	int T; cin>>T;
    310 	while (T--)
    311 	{
    312 		int n,m,i,j;
    313 		cin>>n;
    314 		for (i=1; i<=n; i++)
    315 		{
    316 			e[i].clear();
    317 			id=0;
    318 		}
    319 		for (i=1; i<=n; i++) cin>>w[i];
    320 		for (i=1; i<n; i++)
    321 		{
    322 			int u,v;
    323 			cin>>u>>v;
    324 			e[u].push_back(v);
    325 			e[v].push_back(u);
    326 		}
    327 		dfs(1);
    328 		for (i=1; i<=n; i++) pre[i]=max(pre[i-1],w[nfd[i]]);
    329 		suf[n+1]=0;
    330 		for (i=n; i; i--) suf[i]=max(suf[i+1],w[nfd[i]]);
    331 		int mx=0;
    332 		for (i=1; i<=n; i++) if (max(pre[dfn[i]-1],suf[low[i]+1])>w[i]&&w[i]>w[mx]) mx=i;
    333 		cout<<mx<<'\n';
    334 	}
    335 }
    336 ```
    337 
    338 **Code (Python)**
    339 
    340 ```
    341 for _ in range(int(input())):
    342 	n = int(input())
    343 	w=[int(x) for x in input().split()]
    344 	wb=[[] for i in range(n)]
    345 	for i in range(n):
    346 		w[i]-=1
    347 		wb[w[i]].append(i)
    348 	e=[[] for i in range(n)]
    349 	for i in range(n-1):
    350 		u,v=map(int,input().split())
    351 		e[u-1].append(v-1)
    352 		e[v-1].append(u-1)
    353 	stk=[0]
    354 	f,dfn=[-1]*n,[0]*n
    355 	nfd=[]
    356 	while stk:
    357 		u=stk.pop()
    358 		dfn[u]=len(nfd)
    359 		nfd.append(u)
    360 		for v in e[u]:
    361 			if v!=f[u]:
    362 				f[v]=u
    363 				stk.append(v)
    364 	sz=[1]*n
    365 	nfd.reverse()
    366 	for u in nfd:
    367 		if u==0:
    368 			continue
    369 		sz[f[u]]+=sz[u]
    370 	wb.reverse()
    371 	mx=-1;mn=n+1
    372 	for v in wb:
    373 		for u in v:
    374 			if mn<dfn[u] or mx>dfn[u]+sz[u]-1:
    375 				print(u+1)
    376 				break
    377 		else:
    378 			for u in v:
    379 				mn=min(mn,dfn[u])
    380 				mx=max(mx,dfn[u])
    381 			continue
    382 		break
    383 	else:
    384 		print(0)
    385 ```
    386 
    387 [2062E2 - The Game (Hard Version)](/contest/2062/problem/E2)
    388 
    389 Idea: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"),[SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"),[PaperCloud](/profile/PaperCloud "Master PaperCloud"),[fallleaves01](/profile/fallleaves01 "International Grandmaster fallleaves01"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"),[mejiamejia](/profile/mejiamejia "Expert mejiamejia").
    390 
    391 **Rate this problem**
    392 
    393 Good problem
    394 
    395 Average problem
    396 
    397 Bad problem
    398 
    399 Did not solve
    400 
    401 **Solution**
    402 
    403 Tutorial is loading...
    404 
    405 **Code (C++)**
    406 
    407 ```
    408 #include "bits/stdc++.h"
    409 using namespace std;
    410 #define all(x) (x).begin(),(x).end()
    411 const int N = 5e5 + 2;
    412 vector<int> e[N];
    413 int dfn[N], nfd[N], low[N];
    414 int id, n;
    415 void dfs(int u)
    416 {
    417 	nfd[dfn[u] = ++id] = u;
    418 	for (int v : e[u]) erase(e[v], u), dfs(v);
    419 	low[u] = id;
    420 }
    421 int main()
    422 {
    423 	ios::sync_with_stdio(0); cin.tie(0);
    424 	cout << fixed << setprecision(15);
    425 	int T; cin >> T;
    426 	while (T--)
    427 	{
    428 		int n, m, i, j;
    429 		cin >> n;
    430 		vector w(n, vector<int>());
    431 		vector<int> c(n + 1), ans;
    432 		for (i = 1; i <= n; i++)
    433 		{
    434 			e[i].clear(); id = 0;
    435 			cin >> j;
    436 			w[j - 1].push_back(i);
    437 		}
    438 		for (i = 1; i < n; i++)
    439 		{
    440 			int u, v;
    441 			cin >> u >> v;
    442 			e[u].push_back(v);
    443 			e[v].push_back(u);
    444 		}
    445 		dfs(1);
    446 		int l = n + 1, r = 0;
    447 		set<int> s;
    448 		for (i = n - 1; i >= 0; i--)
    449 		{
    450 			if (s.size())
    451 			{
    452 				for (int u : w[i])
    453 				{
    454 					int mx = 0;
    455 					for (j = dfn[u] - 1; j; j -= j & -j) mx = max(mx, c[j]);
    456 					if ((*s.begin() < dfn[u] || *s.rbegin() > low[u]) && mx <= low[u] && dfn[u] <= l && low[u] >= r)
    457 						ans.push_back(u);
    458 				}
    459 				for (int u : w[i])
    460 				{
    461 					int mn = *s.begin(), mx = *s.rbegin();
    462 					int L = dfn[u], R = low[u];
    463 					if (mn >= L && mx <= R) continue;
    464 					if (mn >= L && mn <= R) mn = *s.upper_bound(R);
    465 					if (mx >= L && mx <= R) mx = *prev(s.lower_bound(L));
    466 					auto fun = [&](int x, int y) {
    467 						if (x > y) swap(x, y);
    468 						l = min(l, y), r = max(r, x);
    469 						for (j = x; j <= n; j += j & -j) c[j] = max(c[j], y);
    470 					};
    471 					fun(mn, dfn[u]);
    472 					fun(mx, dfn[u]);
    473 				}
    474 			}
    475 			for (int u : w[i]) s.insert(dfn[u]);
    476 		}
    477 		sort(all(ans));
    478 		cout << ans.size();
    479 		for (int x : ans) cout << ' ' << x;
    480 		cout << '\n';
    481 	}
    482 }
    483 ```
    484 
    485 [2062F - Traveling Salescat](/contest/2062/problem/F)
    486 
    487 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk").
    488 
    489 **Rate this problem**
    490 
    491 Good problem
    492 
    493 Average problem
    494 
    495 Bad problem
    496 
    497 Did not solve
    498 
    499 **Solution**
    500 
    501 Tutorial is loading...
    502 
    503 **Code (C++)**
    504 
    505 ```
    506 #include<bits/stdc++.h>
    507 using namespace std;
    508 struct apos{
    509 	long long a;
    510 	long long b;
    511 	friend bool operator<(apos a,apos b){
    512 		return a.b-a.a<b.b-b.a;
    513 	}
    514 }ap[3000];
    515 long long dp[3001][3],tdp[3001][3],ans[3001],inf=1000000000000000000LL;
    516 int main(){
    517 	ios::sync_with_stdio(false),cin.tie(0);
    518 	int T,n,i,j,t;
    519 	for(cin>>T;T>0;T--)
    520 	{
    521 		cin>>n;
    522 		for(i=0;i<n;i++)cin>>ap[i].a>>ap[i].b;
    523 		sort(ap,ap+n);
    524 		for(i=0;i<=n;i++)
    525 		{
    526 			for(j=0;j<3;j++)
    527 			{
    528 				dp[i][j]=inf;
    529 				tdp[i][j]=inf;
    530 			}
    531 			ans[i]=inf;
    532 		}
    533 		for(i=0;i<n;i++)
    534 		{
    535 			tdp[1][0]=min(tdp[1][0],ap[i].a*2);
    536 			tdp[1][1]=min(tdp[1][1],ap[i].a);
    537 			for(j=1;j<n;j++)
    538 			{
    539 				for(t=0;t<3;t++)tdp[j+1][t]=min(tdp[j+1][t],dp[j][t]+ap[i].a+ap[i].b);
    540 				tdp[j+1][1]=min(tdp[j+1][1],dp[j][0]+ap[i].b);
    541 				tdp[j+1][2]=min(tdp[j+1][2],dp[j][1]+ap[i].a);
    542 				ans[j+1]=min(ans[j+1],dp[j][1]+ap[i].b);
    543 				ans[j+1]=min(ans[j+1],dp[j][2]+ap[i].b*2);
    544 			}
    545 			for(j=1;j<=n;j++)
    546 			{
    547 				for(t=0;t<3;t++)
    548 				{
    549 					dp[j][t]=min(dp[j][t],tdp[j][t]);
    550 					tdp[j][t]=inf;
    551 				}
    552 			}
    553 		}
    554 		for(i=2;i<=n;i++)cout<<ans[i]<<' ';
    555 		cout<<'\n';
    556 	}
    557 	return 0;
    558 }
    559 ```
    560 
    561 **Code (Python)**
    562 
    563 ```
    564 class Q:
    565 	def __init__(this,x,y):
    566 		this.x,this.y=x+y,x-y
    567 	def __lt__(this,rhs):
    568 		return this.y<rhs.y
    569 for _ in range(int(input())):
    570 	n=int(input())
    571 	a=[0]*n
    572 	for i in range(n):
    573 		x,y=map(int,input().split())
    574 		a[i]=Q(x,y)
    575 	a.sort()
    576 	l=[10**18]*(n+1)
    577 	sl=l.copy();slt=l.copy();slrt=l.copy()
    578 	s=10**18
    579 	for m,t in enumerate(a):
    580 		x,y=t.x,t.y
    581 		for i in range(m,0,-1):
    582 			slrt[i+1]=min(slrt[i+1],sl[i]+x+y,slt[i]+x*2+y*2)
    583 			slt[i+1]=min(slt[i+1],slt[i]+x*2,sl[i]+x-y)
    584 			sl[i+1]=min(sl[i+1],sl[i]+x*2,l[i]+x+y)
    585 			l[i+1]=min(l[i+1],l[i]+x*2)
    586 		sl[1]=min(sl[1],x-y)
    587 		l[1]=min(l[1],x*2-y*2)
    588 	print(*[x//2 for x in slrt[2:]])
    589 ```
    590 
    591 [2062G - Permutation Factory](/contest/2062/problem/G)
    592 
    593 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs").
    594 
    595 **Rate this problem**
    596 
    597 Good problem
    598 
    599 Average problem
    600 
    601 Bad problem
    602 
    603 Did not solve
    604 
    605 **Solution**
    606 
    607 Tutorial is loading...
    608 
    609 **Code (C++)**
    610 
    611 ```
    612 #include<bits/stdc++.h>
    613 using namespace std;
    614 struct linex{
    615 	int v;
    616 	int w;
    617 	int nxt;
    618 	int c;
    619 };
    620 int head[210],cnt,cpos[210],vis[210],qvis[210],totc,dis[210],inf=1000000000;
    621 linex l[21000];
    622 queue<int>que;
    623 void add(int u,int v,int w,int c){
    624 	l[cnt].nxt=head[u];
    625 	head[u]=cnt;
    626 	l[cnt].v=v;
    627 	l[cnt].w=w;
    628 	l[cnt].c=c;
    629 	cnt++;
    630 	l[cnt].nxt=head[v];
    631 	head[v]=cnt;
    632 	l[cnt].v=u;
    633 	l[cnt].w=0;
    634 	l[cnt].c=-c;
    635 	cnt++;
    636 }
    637 int spfa(int st,int en,int n){
    638 	int i,j,t;
    639 	for(i=0;i<n;i++)
    640 	{
    641 		vis[i]=0;
    642 		dis[i]=inf;
    643 		cpos[i]=head[i];
    644 	}
    645 	que.push(st);
    646 	dis[st]=0;
    647 	vis[st]=1;
    648 	qvis[st]=1;
    649 	while(!que.empty())
    650 	{
    651 		t=que.front();
    652 		que.pop();
    653 		qvis[t]=0;
    654 		for(j=head[t];j!=-1;j=l[j].nxt)
    655 		{
    656 			if(l[j].w>0&&dis[l[j].v]>dis[t]+l[j].c)
    657 			{
    658 				dis[l[j].v]=dis[t]+l[j].c;
    659 				vis[l[j].v]=1;
    660 				if(!qvis[l[j].v])
    661 				{
    662 					que.push(l[j].v);
    663 					qvis[l[j].v]=1;
    664 				}
    665 			}
    666 		}
    667 	}
    668 	return vis[en];
    669 }
    670 long long dfs(int p,int en,int curr){
    671 	int x,j,flow=0;
    672 	if(p==en)return curr;
    673 	for(j=cpos[p];j!=-1&&flow<curr;j=l[j].nxt)
    674 	{
    675 		cpos[p]=j;
    676 		qvis[p]=1;
    677 		if(l[j].w>0&&dis[l[j].v]==dis[p]+l[j].c&&!qvis[l[j].v])
    678 		{
    679 			x=dfs(l[j].v,en,min(curr-flow,l[j].w));
    680 			flow+=x;
    681 			l[j].w-=x;
    682 			l[j^1].w+=x;
    683 			totc+=l[j].c*x;
    684 		}
    685 		qvis[p]=0;
    686 	}
    687 	return flow;
    688 }
    689 int p[100],q[100],id[100][100];
    690 int cabs(int x){
    691 	if(x<0)x=-x;
    692 	return x;
    693 }
    694 struct point{
    695 	int x;
    696 	int y;
    697 	int tx;
    698 	int ty;
    699 }pc[100];
    700 vector<int>ansv[2];
    701 int main(){
    702 	ios::sync_with_stdio(false),cin.tie(0);
    703 	srand(time(0));
    704 	int T,n,i,j,flow,flag;
    705 	for(cin>>T;T>0;T--)
    706 	{
    707 		cin>>n;
    708 		for(i=0;i<n;i++)
    709 		{
    710 			cin>>p[i];
    711 			p[i]--;
    712 		}
    713 		for(i=0;i<n;i++)
    714 		{
    715 			cin>>q[i];
    716 			q[i]--;
    717 		}
    718 		for(i=0;i<n*2+2;i++)head[i]=-1;
    719 		cnt=0;
    720 		totc=0;
    721 		flow=0;
    722 		for(i=0;i<n;i++)
    723 		{
    724 			add(n*2,i,1,0);
    725 			add(i+n,n*2+1,1,0);
    726 			for(j=0;j<n;j++)
    727 			{
    728 				id[i][j]=cnt;
    729 				add(i,j+n,1,cabs(i-j)+cabs(p[i]-q[j]));
    730 			}
    731 		}
    732 		while(spfa(n*2,n*2+1,n*2+2))flow+=dfs(n*2,n*2+1,inf);
    733 		for(i=0;i<n;i++)
    734 		{
    735 			pc[i].x=i;
    736 			pc[i].y=p[i];
    737 			for(j=0;j<n;j++)
    738 			{
    739 				if(l[id[i][j]].w==0)
    740 				{
    741 					pc[i].tx=j;
    742 					pc[i].ty=q[j];
    743 				}
    744 			}
    745 		}
    746 		while(1)
    747 		{
    748 			flag=0;
    749 			for(i=0;i<n;i++)
    750 			{
    751 				for(j=0;j<n;j++)
    752 				{
    753 					if(pc[j].tx<=pc[i].x&&pc[i].x<pc[j].x&&pc[j].x<=pc[i].tx)
    754 					{
    755 						ansv[0].push_back(pc[i].x);
    756 						ansv[1].push_back(pc[j].x);
    757 						swap(pc[i].x,pc[j].x);
    758 						flag=1;
    759 					}
    760 				}
    761 			}
    762 			if(!flag)break;
    763 		}
    764 		while(1)
    765 		{
    766 			flag=0;
    767 			for(i=0;i<n;i++)
    768 			{
    769 				for(j=0;j<n;j++)
    770 				{
    771 					if(pc[j].ty<=pc[i].y&&pc[i].y<pc[j].y&&pc[j].y<=pc[i].ty)
    772 					{
    773 						ansv[0].push_back(pc[i].x);
    774 						ansv[1].push_back(pc[j].x);
    775 						swap(pc[i].y,pc[j].y);
    776 						flag=1;
    777 					}
    778 				}
    779 			}
    780 			if(!flag)break;
    781 		}
    782 		cout<<ansv[0].size()<<'\n';
    783 		for(i=0;i<ansv[0].size();i++)cout<<ansv[0][i]+1<<' '<<ansv[1][i]+1<<'\n';
    784 		ansv[0].clear();
    785 		ansv[1].clear();
    786 	}
    787 	return 0;
    788 }
    789 ```
    790 
    791 [2062H - Galaxy Generator](/contest/2062/problem/H)
    792 
    793 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk").
    794 
    795 **Rate this problem**
    796 
    797 Good problem
    798 
    799 Average problem
    800 
    801 Bad problem
    802 
    803 Did not solve
    804 
    805 **Solution**
    806 
    807 Tutorial is loading...
    808 
    809 **Code (C++)**
    810 
    811 ```
    812 #include<bits/stdc++.h>
    813 using namespace std;
    814 const long long mod=1000000007;
    815 string s;
    816 long long dp[15][15][1<<14],vl[200],sgvl[15][15][15][15];
    817 long long dp2[15][1<<14],dpvl2[15][1<<14];
    818 int psum[15][15];
    819 long long getvl(long long l,long long r,long long x,long long y){
    820 	if(l>=r||x>=y)return 0;
    821 	return vl[psum[r][y]-psum[l][y]-psum[r][x]+psum[l][x]];
    822 }
    823 long long f(long long l,long long r,long long x,long long y){
    824 	long long ans=0,i,c,tl,tr,tx,ty;
    825 	for(i=0;i<16;i++)
    826 	{
    827 		c=0;
    828 		tl=l;
    829 		tr=r;
    830 		tx=x;
    831 		ty=y;
    832 		if(i&1)
    833 		{
    834 			c^=1;
    835 			tl++;
    836 		}
    837 		if(i&2)
    838 		{
    839 			c^=1;
    840 			tr--;
    841 		}
    842 		if(i&4)
    843 		{
    844 			c^=1;
    845 			tx++;
    846 		}
    847 		if(i&8)
    848 		{
    849 			c^=1;
    850 			ty--;
    851 		}
    852 		if(c)ans=(ans+mod-getvl(tl,tr,tx,ty))%mod;
    853 		else ans=(ans+getvl(tl,tr,tx,ty))%mod;
    854 	}
    855 	return ans;
    856 }
    857 int main(){
    858 	ios::sync_with_stdio(false),cin.tie(0);
    859 	int T,n,i,j,t,p,l,r,len,cmsk;
    860 	long long ans;
    861 	for(cin>>T;T>0;T--)
    862 	{
    863 		cin>>n;
    864 		vl[0]=0;
    865 		for(i=1;i<=n*n;i++)vl[i]=(vl[i-1]*2+1)%mod;
    866 		for(i=0;i<=n;i++)
    867 		{
    868 			for(j=0;j<=n;j++)psum[i][j]=0;
    869 		}
    870 		for(i=0;i<n;i++)
    871 		{
    872 			cin>>s;
    873 			for(j=0;j<n;j++)psum[i+1][j+1]=s[j]-'0';
    874 		}
    875 		for(i=0;i<n;i++)
    876 		{
    877 			for(j=0;j<=n;j++)psum[i+1][j]+=psum[i][j];
    878 		}
    879 		for(i=0;i<=n;i++)
    880 		{
    881 			for(j=0;j<n;j++)psum[i][j+1]+=psum[i][j];
    882 		}
    883 		for(l=0;l<=n;l++)
    884 		{
    885 			for(r=l+1;r<=n;r++)
    886 			{
    887 				for(i=0;i<=n;i++)
    888 				{
    889 					for(j=i+1;j<=n;j++)sgvl[l][r][i][j]=f(l,r,i,j);
    890 				}
    891 			}
    892 		}
    893 		for(i=0;i<=n;i++)
    894 		{
    895 			for(j=0;j<=n;j++)
    896 			{
    897 				for(t=0;t<(1<<n);t++)dp[i][j][t]=0;
    898 			}
    899 		}
    900 		for(i=0;i<=n;i++)dp[i][i][0]=1;
    901 		for(len=1;len<=n;len++)
    902 		{
    903 			for(l=0;l+len<=n;l++)
    904 			{
    905 				r=l+len;
    906 				for(i=l+1;i<r;i++)
    907 				{
    908 					for(j=1;j<(1<<n);j++)
    909 					{
    910 						for(t=0;t<n;t++)
    911 						{
    912 							cmsk=j;
    913 							for(p=t;p<n&&(j>>p&1^1);p++)
    914 							{
    915 								cmsk|=(1<<p);
    916 								dp[l][r][cmsk]=(dp[l][r][cmsk]+dp[l][i][j]*sgvl[i][r][t][p+1])%mod;
    917 							}
    918 						}
    919 					}
    920 				}
    921 				for(j=1;j<(1<<n);j++)
    922 				{
    923 					for(i=0;(j>>i&1^1);i++);
    924 					for(t=n-1;(j>>t&1^1);t--);
    925 					sgvl[l][r][i][t+1]=(sgvl[l][r][i][t+1]+mod-dp[l][r][j])%mod;
    926 				}
    927 				for(i=0;i<n;i++)
    928 				{
    929 					cmsk=0;
    930 					for(t=i;t<n;t++)
    931 					{
    932 						cmsk|=(1<<t);
    933 						dp[l][r][cmsk]=(dp[l][r][cmsk]+sgvl[l][r][i][t+1])%mod;
    934 					}
    935 				}
    936 				if(len==1)continue;
    937 				for(j=0;j<(1<<n);j++)dp[l][r][j]=(dp[l][r-1][j]+dp[l][r][j])%mod;
    938 			}
    939 		}
    940 		for(i=0;i<=n;i++)
    941 		{
    942 			for(j=0;j<(1<<n);j++)
    943 			{
    944 				dp2[i][j]=0;
    945 				dpvl2[i][j]=0;
    946 			}
    947 		}
    948 		dp2[0][0]=1;
    949 		for(l=0;l<n;l++)
    950 		{
    951 			for(j=0;j<(1<<n);j++)
    952 			{
    953 				dp2[l+1][j]=(dp2[l+1][j]+dp2[l][j])%mod;
    954 				dpvl2[l+1][j]=(dpvl2[l+1][j]+dpvl2[l][j])%mod;
    955 			}
    956 			for(r=l+1;r<=n;r++)
    957 			{
    958 				for(j=0;j<(1<<n);j++)
    959 				{
    960 					for(i=0;i<n;i++)
    961 					{
    962 						cmsk=j;
    963 						for(t=i;t<n&&(j>>t&1^1);t++)
    964 						{
    965 							cmsk|=(1<<t);
    966 							dp2[r][cmsk]=(dp2[r][cmsk]+dp2[l][j]*sgvl[l][r][i][t+1])%mod;
    967 							dpvl2[r][cmsk]=(dpvl2[r][cmsk]+(dp2[l][j]+dpvl2[l][j])*sgvl[l][r][i][t+1])%mod;
    968 						}
    969 					}
    970 				}
    971 			}
    972 		}
    973 		ans=0;
    974 		for(j=1;j<(1<<n);j++)ans=(ans+dpvl2[n][j])%mod;
    975 		cout<<ans<<'\n';
    976 	}
    977 	return 0;
    978 }
    979 ```