C. Unique Number

• Quiz
  • https://codeforces.com/contest/1462/problem/C
• AC
  • https://codeforces.com/contest/1462/submission/101404148
• 解説
  • Find the smallest positive integer というのを読み飛ばしていたので1～9を使うかどうかを「BIT全探索」した結果、期せずして正しい結果になったのでメモしておく
  • 下記画像の通り、上のビットが立ったほうが数値的にも小さくなる

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll T; 
    cin>>T;
    
    map<ll,ll> mp;

    rep(f,1<<9){
      ll v=0;
      ll sum=0;
      rep(i,9){
        if(f>>i&1){
          v *= 10;
          v += (i+1);
          sum += (i+1);
        }
      }
      mp[sum]=v;
    }
    
    while(T--){
      ll v;cin>>v;
      if(mp.count(v)){
        p(mp[v]);
      }else{
        p(-1);
      }
    }

    return 0;
}

別解

• editorialの通りにやるなら9～1の順に見ていって貪欲に採用すればいい

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll T; 
    cin>>T;
    
    while(T--){
      ll v;cin>>v;
      stringstream ss;
      for(int i=9; i>=1; i--){
        if(v>=i){
          v -= i;
          ss<<i;
        }
      }
      if(v==0){
        string s = ss.str();
        reverse(ALL(s));
        p(s);
      }else{
        p(-1);
      }
    }

    return 0;
}