fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Biến "byLen" được đưa ra ngoài thành biến toàn cục
  5. // để cả hàm precompute() và sol() đều có thể truy cập
  6. vector<string> byLen[10];
  7.  
  8. // Hàm này chỉ làm một việc: tính toán trước và điền dữ liệu vào byLen
  9. void precompute() {
  10.     for (int mask = 1; mask < (1<<9); ++mask) {
  11.         string t;
  12.         for (int d = 1; d <= 9; ++d) {
  13.             if (mask & (1<<(d-1))) {
  14.                 t.push_back(char('0' + d));
  15.             }
  16.         }
  17.         byLen[(int)t.size()].push_back(t);
  18.     }
  19.     for (int L = 1; L <= 9; ++L) {
  20.         sort(byLen[L].begin(), byLen[L].end());
  21.     }
  22. }
  23.  
  24. // Hàm sol bây giờ rất gọn gàng, chỉ tập trung vào việc tra cứu
  25. void sol(string s) {
  26.     int L = (int)s.size();
  27.  
  28.     if (L >= 10) {
  29.         cout << "123456789\n";
  30.         return;
  31.     }
  32.  
  33.     auto &vec = byLen[L];
  34.     auto it = upper_bound(vec.begin(), vec.end(), s);
  35.     if (it != vec.begin()) {
  36.         --it;
  37.         cout << *it << '\n';
  38.         return;
  39.     }
  40.  
  41.     if (L == 1) {
  42.         cout << 0 << '\n';
  43.         return;
  44.     }
  45.     cout << byLen[L - 1].back() << '\n';
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(0);
  50.     cin.tie(0);
  51.     cout.tie(0);
  52.  
  53.     // GỌI HÀM TÍNH TOÁN TRƯỚC MỘT LẦN DUY NHẤT
  54.     precompute();
  55.  
  56.     int test;
  57.     cin >> test;
  58.     while(test--) {
  59.         string x;
  60.         cin >> x;
  61.         sol(x);
  62.     }
  63.     return 0;
  64. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout
https://ideone.com/kiP4Iz
language:
C++14 (gcc 8.3)
created:
1 day 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!