fork download
copy 
  1. /*
  2.  *  B. Not Number Theory | SRBD Code Contest - 2024 (Round 1)
  3.  *  Author: Sohom Sahaun | @sohomsahaun | CF: sahaun
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
  10. using ll = long long;
  11.  
  12. const int MX = 1000000;
  13. int bits[MX];
  14. int ans;
  15.  
  16. void pre() {
  17.   int i;
  18.   for (i = 0; i < MX; ++i) {
  19.     bits[i] = __builtin_popcount(i);
  20.   }
  21. }
  22.  
  23. void go(string& s, int ind) {
  24.   if (ind >= (int)s.size()) {
  25.     int num = stoi(s);
  26.     if (bits[num] == bits[ans]) {
  27.       ans = max(ans, num);
  28.     } else if (bits[num] > bits[ans]) {
  29.       ans = num;
  30.     }
  31.     return;
  32.   }
  33.  
  34.   if (s[ind] != '?') {
  35.     go(s, ind+1);
  36.     return;
  37.   }
  38.  
  39.   for (int i = (ind == 0) ? 1 : 0; i <= 9; ++i) {
  40.     string t = s;
  41.     t[ind] = (char)(i+'0');
  42.     go(t, ind+1);
  43.   }
  44. }
  45.  
  46. int main() {
  47.   FAST;
  48.   pre();
  49.  
  50.   int tc = 1, ti;
  51.   cin >> tc;
  52.  
  53.   for (ti = 1; ti <= tc; ++ti) {
  54.     string s;
  55.     cin >> s;
  56.     ans = 0;
  57.     go(s, 0);
  58.     cout << ans << "\n";
  59.   }
  60.  
  61.   return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 7456KB
comments (?)
stdin
copy 
3
??1
?
5?623
stdout
copy 
991
7
58623
https://ideone.com/JpflfE
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!