codeforces-scrape

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

1365.md (7624B)


      1 Source: https://codeforces.com/blog/entry/78504
      2 
      3 [1365A - Matrix Game](/contest/1365/problem/A "Codeforces Round 648 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 #include 
     13 using namespace std;
     14  
     15 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     16 #define endl "\n"
     17 #define int long long
     18 
     19 const int N = 51;
     20 
     21 int n, m;
     22 int a[N][N];
     23 
     24 int32_t main()
     25 {
     26 	IOS;
     27 	int t;
     28 	cin >> t;
     29 	while(t--)
     30 	{
     31 		cin >> n >> m;
     32 		set< int > r, c;
     33 		for(int i = 1; i <= n; i++)
     34 		{
     35 			for(int j = 1; j <= m; j++)
     36 			{
     37 				cin >> a[i][j];
     38 				if(a[i][j] == 1)
     39 					r.insert(i), c.insert(j);
     40 			}
     41 		}
     42 		int mn = min(n — r.size(), m — c.size());
     43 		if(mn % 2)
     44 			cout << "Ashish" << endl;
     45 		else
     46 			cout << "Vivek" << endl;
     47 	}
     48 	return 0;
     49 }
     50 ```
     51 
     52 This problem was prepared by [Ashishgup](/profile/Ashishgup "Master Ashishgup")
     53 
     54 [1365B - Trouble Sort](/contest/1365/problem/B "Codeforces Round 648 (Div. 2)")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Code**
     61 
     62 ```
     63 #include 
     64 using namespace std;
     65  
     66 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     67 #define endl "\n"
     68 #define int long long
     69 
     70 const int N = 1e3 + 5;
     71 
     72 int n;
     73 int a[N], b[N];
     74 
     75 int32_t main()
     76 {
     77 	IOS;
     78 	int t;
     79 	cin >> t;
     80 	while(t--)
     81 	{
     82 		cin >> n;
     83 		bool sorted = 1, have0 = 0, have1 = 0;
     84 		for(int i = 1; i <= n; i++)
     85 		{
     86 			cin >> a[i];
     87 			if(i >= 2 && a[i] < a[i - 1])
     88 				sorted = 0;
     89 		}
     90 		for(int i = 1; i <= n; i++)
     91 		{
     92 			cin >> b[i];
     93 			if(!b[i])
     94 				have0 = 1;
     95 			else
     96 				have1 = 1;
     97 		}
     98 		if(have0 && have1)
     99 			cout << "Yes" << endl;
    100 		else if(sorted)
    101 			cout << "Yes" << endl;
    102 		else
    103 			cout << "No" << endl;
    104 	}
    105 	return 0;
    106 }
    107 ```
    108 
    109 This problem was prepared by [Ashishgup](/profile/Ashishgup "Master Ashishgup")
    110 
    111 [1365C - Rotation Matching](/contest/1365/problem/C "Codeforces Round 648 (Div. 2)")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Code**
    118 
    119 ```
    120 #include 
    121 using namespace std;
    122  
    123 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    124 #define endl "\n"
    125 #define int long long
    126 
    127 const int N = 2e5 + 5;
    128 
    129 int n;
    130 int a[N], b[N], pos[N];
    131 map< int, int > offset;
    132 
    133 int32_t main()
    134 {
    135 	IOS;
    136 	cin >> n;
    137 	for(int i = 1; i <= n; i++)
    138 	{
    139 		cin >> a[i];
    140 		pos[a[i]] = i;
    141 	}
    142 	for(int i = 1; i <= n; i++)
    143 		cin >> b[i];
    144 	for(int i = 1; i <= n; i++)
    145 	{
    146 		int cur = pos[b[i]] - i;
    147 		if(cur < 0)
    148 			cur += n;
    149 		offset[cur]++;
    150 	}
    151 	int ans = 0;
    152 	for(auto &it:offset)
    153 		ans = max(ans, it.second);
    154 	cout << ans;
    155 	return 0;
    156 }
    157 ```
    158 
    159 This problem was prepared by [Ashishgup](/profile/Ashishgup "Master Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10")
    160 
    161 [1365D - Solve The Maze](/contest/1365/problem/D "Codeforces Round 648 (Div. 2)")
    162 
    163 **Tutorial**
    164 
    165 Tutorial is loading...
    166 
    167 **Code**
    168 
    169 ```
    170 #include 
    171 using namespace std;
    172 #define int long long
    173 typedef int ll;
    174 typedef long double ld;
    175 const ll N = 55;
    176 char en = '\n';
    177 ll inf = 1e16;
    178 ll mod = 1e9 + 7;
    179 ll power(ll x, ll n, ll mod) {
    180   ll res = 1;
    181   x %= mod;
    182   while (n) {
    183     if (n & 1)
    184       res = (res * x) % mod;
    185     x = (x * x) % mod;
    186     n >>= 1;
    187   }
    188   return res;
    189 }
    190 ll n, m;
    191 char arr[N][N];
    192 ll dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    193 
    194 bool valid(ll i, ll j) { return i >= 1 && i <= n && j >= 1 && j <= m; }
    195 int32_t main() {
    196   ios_base::sync_with_stdio(false);
    197   cin.tie(NULL);
    198 
    199   ll t;
    200   cin >> t;
    201   while (t--) {
    202 
    203     cin >> n >> m;
    204 
    205     for (ll i = 1; i <= n; i++) {
    206       cin >> (arr[i] + 1);
    207     }
    208 
    209     for (ll i = 1; i <= n; i++) {
    210       for (ll j = 1; j <= m; j++) {
    211         if (arr[i][j] == 'B') {
    212           for (ll k = 0; k < 4; k++) {
    213             ll ni = i + dir[k][0];
    214             ll nj = j + dir[k][1];
    215             if (valid(ni, nj) && arr[ni][nj] == '.')
    216               arr[ni][nj] = '#';
    217           }
    218         }
    219       }
    220     }
    221 
    222     queue> que;
    223     bool visited[n + 5][m + 5];
    224     memset(visited, false, sizeof(visited));
    225     if (arr[n][m] == '.') {
    226       que.push({n, m});
    227       visited[n][m] = true;
    228     }
    229     while (!que.empty()) {
    230       pair curr = que.front();
    231       que.pop();
    232       for (ll k = 0; k < 4; k++) {
    233         ll ni = curr.first + dir[k][0];
    234         ll nj = curr.second + dir[k][1];
    235         if (valid(ni, nj) && !visited[ni][nj] && arr[ni][nj] != '#') {
    236           que.push({ni, nj});
    237           visited[ni][nj] = true;
    238         }
    239       }
    240     }
    241     bool good = true;
    242     for (ll i = 1; i <= n; i++) {
    243       for (ll j = 1; j <= m; j++) {
    244         if ((arr[i][j] == 'G' && !visited[i][j]) or
    245             (arr[i][j] == 'B' && visited[i][j])) {
    246           good = false;
    247           break;
    248         }
    249       }
    250     }
    251     cout << (good ? "Yes" : "No") << en;
    252   }
    253 
    254   return 0;
    255 }
    256 ```
    257 
    258 This problem was prepared by [Vivek1998299](/profile/Vivek1998299 "Master Vivek1998299")
    259 
    260 [1365E - Maximum Subsequence Value](/contest/1365/problem/E "Codeforces Round 648 (Div. 2)")
    261 
    262 **Tutorial**
    263 
    264 Tutorial is loading...
    265 
    266 **Code**
    267 
    268 ```
    269 #include 
    270 using namespace std;
    271  
    272 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    273 #define endl "\n"
    274 #define int long long
    275 
    276 const int N = 505;
    277 
    278 int n;
    279 int a[N];
    280 
    281 int32_t main()
    282 {
    283 	IOS;
    284 	cin >> n;
    285 	for(int i = 1; i <= n; i++)
    286 		cin >> a[i];
    287 	int ans = 0;
    288 	for(int i = 1; i <= n; i++)
    289 		for(int j = i; j <= n; j++)
    290 			for(int k = j; k <= n; k++)
    291 				ans = max(ans, (a[i] | a[j] | a[k]));
    292 	cout << ans;
    293 	return 0;
    294 }
    295 ```
    296 
    297 This problem was prepared by [Ashishgup](/profile/Ashishgup "Master Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10")
    298 
    299 [1365F - Swaps Again](/contest/1365/problem/F "Codeforces Round 648 (Div. 2)")
    300 
    301 **Tutorial**
    302 
    303 Tutorial is loading...
    304 
    305 **Code**
    306 
    307 ```
    308 #include
    309 using namespace std;
    310 
    311 int main(){
    312 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    313 	int tc;
    314 	cin >> tc;
    315 	while(tc--){
    316 		int n;
    317 		cin >> n;
    318 		map< pair < int, int >, int > pairs;
    319 		vector< int > a(n), b(n);
    320 		bool possible = 1;
    321 
    322 		for(int i = 0; i < n; i++)
    323 			cin >> a[i];
    324 
    325 		for(int i = 0; i < n; i++)
    326 			cin >> b[i];
    327 
    328 		if(n % 2 == 1 && a[n / 2] != b[n / 2])
    329 			possible = 0;
    330 
    331 		for(int i = 0; i < n / 2; i++){
    332 			pair< int, int > p = {min(a[i], a[n — 1 — i]), max(a[i], a[n — 1 — i])};
    333 			pairs[p]++;
    334 		}
    335 
    336 		for(int i = 0; i < n / 2; i++){
    337 			pair< int, int > p = {min(b[i], b[n — 1 — i]), max(b[i], b[n — 1 — i])};
    338 			if(pairs[p] <= 0)
    339 				possible = 0;
    340 			pairs[p]--;
    341 		}
    342 
    343 		if(possible)
    344 			cout << "Yes" << endl;
    345 
    346 		else cout << "No" << endl;
    347 	}
    348 }
    349 ```
    350 
    351 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger"), [Ashishgup](/profile/Ashishgup "Master Ashishgup") and [Vivek1998299](/profile/Vivek1998299 "Master Vivek1998299")
    352 
    353 [1365G - Secure Password](/contest/1365/problem/G "Codeforces Round 648 (Div. 2)")
    354 
    355 **Tutorial**
    356 
    357 Tutorial is loading...
    358 
    359 **Code**
    360 
    361 ```
    362 #include
    363 using namespace std;
    364 
    365 #define ll long long
    366 #define vint vector< int >
    367 
    368 const int Q = 13;
    369 
    370 ll query(vint v){
    371 	cout << "? " << v.size() << ' ';
    372 	for(ll i : v)
    373 		cout << i + 1 << ' ';
    374 	cout << endl;
    375 	fflush(stdout);
    376 	ll or_value;
    377 	cin >> or_value;
    378 	return or_value;
    379 }
    380 
    381 int main(){
    382 	int n;
    383 	cin >> n;
    384 
    385 	vector< vint > ask(Q);
    386 	vint assign_mask(n);
    387 
    388 	vector< ll > or_value(Q), answer(n);
    389 
    390 	int assigned = 0;
    391 
    392 	for(int i = 1; i < (1 << Q); i++){
    393 		if(__builtin_popcount(i) != Q / 2)
    394 			continue;
    395 		assign_mask[assigned] = i;
    396 		for(int j = 0; j < Q; j++)
    397 			if((i >> j & 1) == 0)
    398 				ask[j].push_back(assigned);
    399 		assigned++;
    400 		if(assigned == n)
    401 			break;
    402 	}
    403 
    404 	for(int i = 0; i < Q; i++)
    405 		if(!ask[i].empty())
    406 			or_value[i] = query(ask[i]);
    407 
    408 	for(int i = 0; i < n; i++)
    409 		for(int j = 0; j < Q; j++)
    410 			if(assign_mask[i] >> j & 1)
    411 				answer[i] |= or_value[j];
    412 
    413 	cout << "! ";
    414 
    415 	for(ll i : answer)
    416 		cout << i << ' ';
    417 
    418 	cout << endl;
    419 }
    420 ```
    421 
    422 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger")