1348.md (7497B)
1 Source: https://codeforces.com/blog/entry/76555 2 3 [1348A - Phoenix and Balance](/contest/1348/problem/A "Codeforces Round 638 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 void solve(){ 16 int N; 17 cin>>N; 18 //note: 1<<X means 2^X 19 //we put largest coin in first pile 20 int sum1=(1<<N), sum2=0; 21 //we put n/2-1 smallest coins in first pile 22 for (int i=1;i<N/2;i++) 23 sum1+=(1<<i); 24 //we put remaining n/2 coins in second pile 25 for (int i=N/2;i<N;i++) 26 sum2+=(1<<i); 27 cout<<sum1-sum2<<endl; 28 } 29 30 int main(){ 31 int t; cin>>t; 32 while (t--) 33 solve(); 34 } 35 ``` 36 37 [1348B - Phoenix and Beauty](/contest/1348/problem/B "Codeforces Round 638 (Div. 2)") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 using namespace std; 48 49 void solve(){ 50 int N,K; 51 cin>>N>>K; 52 set<int>s; 53 for (int i=0;i<N;i++){ 54 int a; 55 cin>>a; 56 s.insert(a); 57 } 58 //if more than K distinct numbers, print -1 59 if (s.size()>K){ 60 cout<<-1<<endl; 61 return; 62 } 63 cout<<N*K<<endl; 64 for (int i=0;i<N;i++){ 65 //print the distinct numbers 66 for (int b:s) 67 cout<<b<<' '; 68 //print the extra 1s 69 for (int j=0;j<K-(int)s.size();j++) 70 cout<<1<<' '; 71 } 72 cout<<endl; 73 } 74 75 int main(){ 76 int t; cin>>t; 77 while (t--) 78 solve(); 79 } 80 ``` 81 82 [1348C — Phoenix and Distribution](https://codeforces.com/contest/1348/problem/C) 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution** 89 90 ``` 91 #include <bits/stdc++.h> 92 using namespace std; 93 94 void solve(){ 95 int n,k; 96 cin>>n>>k; 97 string s; 98 cin>>s; 99 sort(s.begin(),s.end()); 100 //if smallest k letters are not all the same, answer is kth smallest letter 101 if (s[0]!=s[k-1]){ 102 cout<<s[k-1]<<endl; 103 return; 104 } 105 cout<<s[0]; 106 //if remaining letters aren't the same, we append remaining letters to answer 107 if (s[k]!=s[n-1]){ 108 for (int i=k;i<n;i++) 109 cout<<s[i]; 110 } 111 else{ 112 //remaining letters are the same, so we distribute evenly 113 for (int i=0;i<(n-k+k-1)/k;i++) 114 cout<<s[n-1]; 115 } 116 cout<<endl; 117 } 118 119 int main(){ 120 int t; cin>>t; 121 while (t--) 122 solve(); 123 } 124 ``` 125 126 [1348D - Phoenix and Science](/contest/1348/problem/D "Codeforces Round 638 (Div. 2)") 127 128 **Tutorial** 129 130 Tutorial is loading... 131 132 **Solution** 133 134 ``` 135 #include <bits/stdc++.h> 136 using namespace std; 137 138 void solve(){ 139 vector<int>inc; 140 int N; 141 cin>>N; 142 //construct sequence 1, 2, 4, ... while sum <= N 143 for (int i=1;i<=N;i*=2){ 144 inc.push_back(i); 145 N-=i; 146 } 147 //if sum is not N, we insert and sort 148 if (N>0){ 149 inc.push_back(N); 150 sort(inc.begin(),inc.end()); 151 } 152 cout<<inc.size()-1<<endl; 153 for (int i=1;i<(int)inc.size();i++) 154 cout<<inc[i]-inc[i-1]<<' '; 155 cout<<endl; 156 } 157 158 int main(){ 159 int t; cin>>t; 160 while (t--) 161 solve(); 162 } 163 ``` 164 165 [1348E - Phoenix and Berries](/contest/1348/problem/E "Codeforces Round 638 (Div. 2)") 166 167 **Tutorial** 168 169 Tutorial is loading... 170 171 **Solution** 172 173 ``` 174 //Solution 1 175 #include <bits/stdc++.h> 176 using namespace std; 177 178 int N,K; 179 int a[505],b[505]; 180 bool dp[505][505]; //number of shrubs considered, "extra" red berries 181 182 int main(){ 183 cin>>N>>K; 184 long long totA=0,totB=0; 185 for (int i=1;i<=N;i++){ 186 cin>>a[i]>>b[i]; 187 totA+=a[i]; 188 totB+=b[i]; 189 } 190 dp[0][0]=true; 191 for (int i=1;i<=N;i++){ 192 for (int j=0;j<K;j++){ 193 //leave a[i]%K extra red berries 194 dp[i][j]=dp[i-1][(j-a[i]%K+K)%K]; 195 for (int l=0;l<=min(K-1,a[i]);l++){ 196 //check if we can leave l extra red berries 197 if ((a[i]-l)%K+b[i]>=K) 198 dp[i][j]|=dp[i-1][(j-l+K)%K]; 199 } 200 } 201 } 202 long long ans=0; 203 for (int i=0;i<K;i++){ 204 if (dp[N][i]) 205 ans=max(ans,(totA+totB-i)/K); 206 } 207 cout<<ans<<endl; 208 } 209 ``` 210 211 [1348F - Phoenix and Memory](/contest/1348/problem/F "Codeforces Round 638 (Div. 2)") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution 1** 218 219 ``` 220 #include <bits/stdc++.h> 221 using namespace std; 222 223 const int INF=1e9+7; 224 225 int as[200005], bs[200005]; 226 227 vector<pair<int,int> > start[200005]; 228 int ans[200005]; 229 int where[200005]; 230 int N; 231 232 void show(){ 233 for(int i=1;i<=N;i++) 234 cout<<ans[i]<<' '; 235 cout<<endl; 236 } 237 238 pair<int,int> st[400005]; 239 240 int query(int l,int r){ 241 l--; 242 pair<int,int> res{INF,INF}; 243 for(l+=N,r+=N;l<r;l>>=1,r>>=1){ 244 if(l&1) res=min(res,st[l++]); 245 if(r&1) res=min(res,st[--r]); 246 } 247 return res.second; 248 } 249 250 int main(){ 251 cin>>N; 252 for(int i=1;i<=N;i++){ 253 cin>>as[i]>>bs[i]; 254 start[as[i]].push_back({bs[i],i}); 255 } 256 set<pair<int,int> > active;//(right,index) 257 for(int i=1;i<=N;i++){ 258 active.insert(start[i].begin(),start[i].end()); 259 ans[active.begin()->second]=i; 260 where[i]=active.begin()->second; 261 active.erase(active.begin()); 262 } 263 for(int i=0;i<N;i++){ 264 st[i+N]={as[where[i+1]],i+1}; 265 } 266 for(int i=N-1;i>0;i--){ 267 st[i]=min(st[i<<1],st[i<<1|1]); 268 } 269 for(int i=1;i<=N;i++){ 270 int j=query(i+1,bs[where[i]]); 271 if(j==INF) continue; 272 if(as[where[j]]<=i){ 273 cout<<"NO"<<endl; 274 show(); 275 swap(ans[where[i]],ans[where[j]]); 276 show(); 277 return 0; 278 } 279 } 280 cout<<"YES"<<endl; 281 show(); 282 } 283 ``` 284 285 **Solution 2** 286 287 ``` 288 #include <bits/stdc++.h> 289 using namespace std; 290 291 int N; 292 int a[200005],b[200005]; 293 int label[200005]; //the label of the person at i-th position in our perfect matching 294 int label2[200005]; //which position the i-th person is at 295 296 void perfectMatch(){ //finds a perfect matching 297 deque<pair<pair<int,int>,int>>v; 298 for (int i=1;i<=N;i++) 299 v.push_back({{a[i],b[i]},i}); 300 sort(v.begin(),v.end()); 301 multiset<pair<int,int>>mst; 302 for (int i=1;i<=N;i++){ 303 while ((int)v.size()>0 && v[0].first.first<=i){ 304 mst.insert({v[0].first.second,v[0].second}); 305 v.pop_front(); 306 } 307 //match person with label to earliest ending interval 308 label2[i]=mst.begin()->second; 309 label[mst.begin()->second]=i; 310 mst.erase(mst.find(*mst.begin())); 311 } 312 } 313 314 set<int>active; 315 int vis[200005]; 316 int from[200005]; 317 int ans[200005]; 318 319 void foundAnother(int node, int nextNode){ 320 vector<int>v; 321 int cur=node; 322 //backtracks on cycle to find other ordering 323 while (cur!=label2[nextNode]){ 324 v.push_back(cur); 325 cur=from[cur]; 326 } 327 reverse(v.begin(),v.end()); 328 v.push_back(label2[nextNode]); 329 reverse(v.begin(),v.end()); 330 cout<<"NO"<<endl; 331 for (int i=1;i<=N;i++) 332 cout<<label[i]<<' '; 333 cout<<endl; 334 for (int i=1;i<=N;i++) 335 ans[i]=label[i]; 336 int temp=ans[v.back()]; 337 for (int i=0;i<(int)v.size();i++) 338 swap(temp,ans[v[i]]); 339 for (int i=1;i<=N;i++) 340 cout<<ans[i]<<' '; 341 cout<<endl; 342 exit(0); 343 } 344 345 void dfs(int node){ 346 //activates node 347 vis[node]=1; 348 queue<int>toRemove; 349 for (;;){ 350 //binary search for unvisisited neighbor 351 auto it=active.lower_bound(a[node]); 352 if (it!=active.end() && *it==label[node]){ 353 toRemove.push(*it); 354 it++; 355 } 356 if (it==active.end() || *it>b[node]) 357 break; 358 if (vis[label2[*it]]==1) //found cycle (another ordering) 359 foundAnother(node,*it); 360 toRemove.push(*it); 361 if (vis[label2[*it]]==2) 362 continue; 363 from[label2[*it]]=node; 364 dfs(label2[*it]); 365 } 366 //removes visited nodes from set 367 while (!toRemove.empty()){ 368 if (active.count(toRemove.front())) 369 active.erase(toRemove.front()); 370 toRemove.pop(); 371 } 372 //deactivates and retire node 373 vis[node]=2; 374 } 375 376 int main(){ 377 cin>>N; 378 for (int i=1;i<=N;i++) 379 cin>>a[i]>>b[i]; 380 perfectMatch(); 381 for (int i=1;i<=N;i++) 382 active.insert(i); 383 for (int i=1;i<=N;i++) 384 if (vis[i]==0) 385 dfs(i); 386 cout<<"YES"<<endl; 387 for (int i=1;i<=N;i++) 388 cout<<label[i]<<' '; 389 cout<<endl; 390 } 391 ```