codeforces-scrape

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

1481.md (7832B)


      1 Source: https://codeforces.com/blog/entry/87523
      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 t;cin>>t;
     14     while(t--){
     15         int x,y;cin>>x>>y;
     16         string s;cin>>s;
     17         int u=0,d=0,l=0,r=0;
     18         for(int i=0;i<s.length();i++){
     19             if(s[i]=='U')u++;
     20             else if(s[i]=='R')r++;
     21             else if(s[i]=='D')d++;
     22             else l++;
     23         }
     24         if(x > 0 && r >= x )x = 0;
     25         if(x < 0 && l >= -x )x = 0;
     26         if(y > 0 && u >= y )y = 0;
     27         if(y < 0 && d >= -y )y = 0;
     28         cout<<((!x && !y)?"YES":"NO")<<endl;
     29     }
     30 }
     31 ```
     32 
     33 Author: [Salem_Alwarawreh](/profile/Salem_Alwarawreh "Expert Salem_Alwarawreh")
     34 
     35 Tutorial is loading...
     36 
     37 **code**
     38 
     39 ```
     40 #include <bits/stdc++.h>
     41 
     42 using namespace std;
     43 
     44 #define all(x) (x).begin(), (x).end()
     45 #define fast ios::sync_with_stdio(false);cin.tie(0);
     46 typedef long long ll;
     47 typedef long double ld;
     48 typedef unsigned long long ull;
     49 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     50 
     51 int main(){
     52 	fast
     53 	int t;
     54 	cin>>t;
     55 	while(t--){
     56 		int n,k;
     57 		cin>>n>>k;
     58 		vector<int> a(n);
     59 		for(int i=0;i<n;i++)cin>>a[i];
     60 		int mx = *max_element(all(a));
     61 		if(n * mx < k){
     62 			cout << -1 << '\n';
     63 			continue;
     64 		}
     65 		int ans = n+1;
     66 		for(int b=0;b<k;b++){
     67 			int to = -2;
     68 			for(int i=0;i<n-1;i++){
     69 				if(a[i] < a[i+1]){
     70 					to = i;
     71 					break;
     72 				}
     73 			}
     74 			ans = to + 1;
     75 			if(to == -2)break;
     76 			a[to]++;
     77 		}
     78 		cout << ans << '\n';
     79 	}	
     80 }
     81 ```
     82 
     83 Author: [Warawreh](/profile/Warawreh "Master Warawreh")
     84 
     85 Tutorial is loading...
     86 
     87 **code**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 using namespace std;
     92 #define mod 1000000007
     93 #define oo 1000000010
     94 const int N = 300010;
     95 
     96 int n , m;
     97 
     98 int a[N] , b[N] , c[N] , ans[N];
     99 
    100 vector< int > g[N];
    101 
    102 void solve(){
    103 	scanf("%d%d",&n,&m);
    104 	for(int i = 1 ;i <= n;i++) g[i].clear();
    105 	for(int i = 0 ;i < n;i++)
    106 		scanf("%d",&a[i]);
    107 	for(int i = 0 ;i < n;i++){
    108 		scanf("%d",&b[i]);
    109 		if(b[i] != a[i])
    110 			g[b[i]].push_back(i);
    111 	}
    112 	for(int i = 0; i < m;i++){
    113 		scanf("%d",&c[i]);
    114 	}
    115 	int last = -1;
    116 	if((int)g[c[m - 1]].size() > 0){
    117 		last = g[c[m - 1]].back();
    118 		g[c[m - 1]].pop_back();
    119 	}
    120 	else{
    121 		for(int i = 0 ;i < n;i++){
    122 			if(b[i] == c[m - 1]){
    123 				last = i;
    124 				break;
    125 			}
    126 		}
    127 	}
    128 	if(last == -1){
    129 		puts("NO");
    130 		return;
    131 	}
    132 	ans[m - 1] = last;
    133 	for(int i = 0 ;i < m - 1;i++){
    134 		if((int)g[c[i]].size() == 0){
    135 		 	ans[i] = last;
    136 		}
    137 		else{
    138 			ans[i] = g[c[i]].back();
    139 			g[c[i]].pop_back();
    140 		}
    141 	}
    142 	for(int i = 1;i <= n;i++){
    143 		if((int)g[i].size() > 0){
    144 			puts("NO");
    145 			return;
    146 		}
    147 	}
    148 	puts("YES");
    149 	for(int i = 0 ;i < m;i++){
    150 		if(i) putchar(' ');
    151 		printf("%d",ans[i] + 1);
    152 	}
    153 	puts("");
    154 }
    155 
    156 int main(){
    157 	int t;
    158 	cin >> t;
    159 	while(t--)
    160 		solve();
    161 	return 0;
    162 }
    163 ```
    164 
    165 Author: [AntiBsayer](/profile/AntiBsayer "Grandmaster AntiBsayer")
    166 
    167 Preperation: [Warawreh](/profile/Warawreh "Master Warawreh")
    168 
    169 Tutorial is loading...
    170 
    171 **code**
    172 
    173 ```
    174 #include <bits/stdc++.h>
    175 using namespace std;
    176 #define mod 998244353
    177 #define oo 1000000010
    178 const int N = 1010;
    179 int n , m;
    180 char grid[N][N];
    181 int has[N][2];
    182 
    183 void solve(){
    184 	scanf("%d%d",&n,&m);
    185 	for(int i = 0 ;i <= n;i++) has[i][0] = has[i][1] = -1;
    186 	for(int i = 0 ;i < n;i++){
    187 		scanf("%s",grid[i]);
    188 		for(int j = 0  ;j < n;j++){
    189 			if(j == i) continue;
    190 			has[i][grid[i][j] - 'a'] = j;
    191 		}
    192 	}
    193 	if(m & 1){
    194 		puts("YES");
    195 		for(int i = 0 ;i < m + 1;i++){
    196 			if(i) putchar(' ');
    197 			printf("%d",(i & 1) + 1);
    198 		}
    199 		puts("");
    200 		return;
    201 	}
    202 	for(int i = 0 ;i < n;i++){
    203 		for(int j = i + 1;j < n;j++){
    204 			if(grid[i][j] == grid[j][i]){
    205 				puts("YES");
    206 				for(int k = 0 ;k < m + 1;k++){
    207 					if(k) putchar(' ');
    208 					printf("%d",(k & 1 ? i + 1 : j + 1));
    209 				}
    210 				puts("");
    211 				return;
    212 			}
    213 		}
    214 	}
    215 	for(int i = 0 ;i < n;i++){
    216 		for(int j = 0;j < n;j++){
    217 		    if(i == j) continue;
    218 			if(has[j][grid[i][j] - 'a'] == -1) continue;
    219 			puts("YES");
    220 			int cur = has[j][grid[i][j] - 'a'];
    221 			if((m / 2) % 2 == 1){
    222 				for(int k = 0 ;k < m + 1;k++){
    223 					if(k) putchar(' ');
    224 					if(k % 4 == 0)
    225 						printf("%d",i + 1);
    226 					else if(k % 4 == 2)
    227 						printf("%d",cur + 1);
    228 					else
    229 						printf("%d",j + 1);
    230 				}
    231 				puts("");
    232 				return;
    233 			}
    234 			printf("%d",j + 1);
    235 			for(int k = 0 ;k < m / 2;k++){
    236 				if(k & 1) printf(" %d",j + 1); else printf(" %d",cur + 1);
    237 			}
    238 			for(int k = 0 ;k < m / 2;k++){
    239 				if(k & 1) printf(" %d",j + 1); else printf(" %d",i + 1);
    240 			}
    241 			puts("");
    242 			return;			
    243 		}
    244 	}
    245 	puts("NO");
    246 	return;
    247 }
    248 
    249 int main(){
    250 	int t;
    251 	scanf("%d",&t);
    252 	while(t--)
    253 	    solve();
    254 	return 0;
    255 }
    256 ```
    257 
    258 Author: [AntiBsayer](/profile/AntiBsayer "Grandmaster AntiBsayer")
    259 
    260 Tutorial is loading...
    261 
    262 **code**
    263 
    264 ```
    265 #include <bits/stdc++.h>
    266 
    267 using namespace std;
    268 
    269 #define all(x) (x).begin(), (x).end()
    270 #define fast ios::sync_with_stdio(false);cin.tie(0);
    271 typedef long long ll;
    272 typedef long double ld;
    273 typedef unsigned long long ull;
    274 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    275 
    276 int main(){
    277 	fast
    278 	int n;
    279 	cin>>n;
    280 	vector<int> a(n),f(n),cf(n);
    281 	vector<pair<int,int>> at(n,{-1,-1});
    282 	for(int i=0;i<n;i++){
    283 		cin>>a[i];
    284 		a[i]--;
    285 		f[a[i]]++;
    286 		if(at[a[i]].first == -1)at[a[i]] = {i,i};
    287 		at[a[i]].second = i;
    288 	}
    289 	vector<int> dp(n+1);
    290 
    291 	for(int i=n-1;i>=0;i--){
    292 		dp[i] = dp[i+1];
    293 		cf[a[i]]++;
    294 		if(i == at[a[i]].first)dp[i] = max(dp[i] , dp[at[a[i]].second + 1] + f[a[i]]);
    295 		else dp[i] = max(dp[i] , cf[a[i]]);
    296 	}
    297 
    298 	cout << n - dp[0] << '\n';
    299 }
    300 ```
    301 
    302 Author: [Warawreh](/profile/Warawreh "Master Warawreh")
    303 
    304 Tutorial is loading...
    305 
    306 **code**
    307 
    308 ```
    309 #include <bits/stdc++.h>
    310 using namespace std;
    311 #define mod 998244353
    312 #define oo 1000000010
    313 const int N = 100010;
    314 const int SQ = 500;
    315 int n , x , p;
    316 vector< int > g[N] , cur[N];
    317 
    318 char c[N];
    319 
    320 int mx;
    321 
    322 vector< pair<int,int> > v , v2;
    323 
    324 pair< int , char > a , b;
    325 
    326 int sz[N];
    327 
    328 bool comp(int u,int v){
    329 	return (sz[u] < sz[v]);
    330 }
    331 
    332 int DFS(int node,int d){
    333 	mx = max(mx,d);
    334 	cur[d].push_back(node);
    335 	sz[node] = 1;
    336 	for(int i = 0 ;i < (int)g[node].size();i++)
    337 		sz[node] += DFS(g[node][i] , d + 1);	
    338 	return sz[node];
    339 }
    340 
    341 bool dp[SQ][N];
    342 
    343 int f[N];
    344 
    345 void build_path(int i,int j){
    346 	if(i == (int)v2.size())
    347 		return;
    348 	while(!dp[i + 1][j]){
    349 		f[v2[i].first]++;
    350 		j -= v2[i].first;
    351 	}
    352 	build_path(i + 1 , j);
    353 }
    354 
    355 int main(){
    356 	scanf("%d%d",&n,&x);
    357 	a = make_pair(x , 'a');
    358 	b = make_pair(n - x , 'b');
    359 	if(a > b) swap(a , b);
    360 	for(int i = 2 ;i <= n;i++){
    361 		scanf("%d",&p);
    362 		g[p].push_back(i);
    363 	}
    364 	DFS(1 , 0);
    365 	for(int i = 0 ;i <= mx;i++)
    366 		v.push_back(make_pair((int)cur[i].size() , i));
    367 	sort(v.begin(),v.end());
    368 	for(int i = 0 ;i < (int)v.size();i++){
    369 		if(i == 0 || v[i].first != v[i - 1].first)
    370 			v2.push_back(make_pair(v[i].first , 1));
    371 		else
    372 			v2.back().second++;
    373 	}
    374 	dp[(int)v2.size()][0] = true;
    375 	int val , frq;
    376 	for(int i = (int)v2.size() - 1;i >= 0;i--){
    377 		val = v2[i].first;
    378 		frq = v2[i].second;
    379 		vector< int > last(val , -1);
    380 		for(int j = 0 ;j <= a.first;j++){
    381 			if(dp[i + 1][j] == true)
    382 				last[j % val] = j;
    383 			if(last[j % val] == -1 || ((j - last[j % val]) / val) > frq)
    384 				dp[i][j] = false;
    385 			else
    386 				dp[i][j] = true;
    387 		}
    388 	}
    389 	if(dp[0][a.first]){
    390 		build_path(0 , a.first);
    391 		for(int i = 1;i <= n;i++) c[i - 1] = b.second;
    392 		for(int i = 0 ;i <= mx;i++){
    393 			if(f[(int)cur[i].size()] == 0) continue;
    394 			f[(int)cur[i].size()]--;
    395 			for(int j = 0 ;j < (int)cur[i].size();j++)
    396 				c[cur[i][j] - 1] = a.second;
    397 		}
    398 		printf("%d\n",mx + 1);
    399 		c[n] = '\0';
    400 		puts(c);
    401 		return 0;	
    402 	}
    403 	printf("%d\n",mx + 2);
    404 	for(int i = 0 ;i <= mx;i++){
    405 		sort(cur[i].begin(),cur[i].end(),comp);
    406 		if(a.first < b.first) swap(a , b);
    407 		while((int)cur[i].size() > 0 && a.first > 0){
    408 			c[cur[i].back() - 1] = a.second;
    409 			cur[i].pop_back();
    410 			a.first--;
    411 		}
    412 		while((int)cur[i].size() > 0 && b.first > 0){
    413 			c[cur[i].back() - 1] = b.second;
    414 			cur[i].pop_back();
    415 			b.first--;
    416 		}
    417 	}
    418 	c[n] = '\0';
    419 	puts(c);
    420 	return 0;
    421 }
    422 ```
    423 
    424 Author: [AntiBsayer](/profile/AntiBsayer "Grandmaster AntiBsayer")