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")