Advertisement
BaoJIaoPisu

Untitled

Aug 6th, 2021
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  29. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  30.  
  31. const ll oo = 1e18;
  32. const ll maxN = 1e6;
  33.  
  34. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  35.  
  36. void maximize(int &a, int b) {
  37.     a = max(a, b);
  38. }
  39.  
  40. void minimize(int &a, int b) {
  41.     a = min(a, b);
  42. }
  43.    
  44. int res = 0;
  45. int a[100], cnt[100];
  46.  
  47. void f(string s, int len, int x, int c, int k) {
  48.     if(len > x) return;
  49.     if(len == x) {
  50.         do {
  51.             res++;
  52.             printf("%s ", s.c_str());
  53.             if(res == k) return;
  54.         } while(next_permutation(s.begin(), s.end()));
  55.         cnt[c]--;
  56.         return;
  57.     }
  58.  
  59.     for(int i = max(1, c); i <= 26; i++) {
  60.         if(cnt[i] < a[i]) {
  61.             cnt[i]++;
  62.             f(s + (char)(i + 'a' - 1), len + 1, x, i, k);
  63.             if(res == k) return;
  64.         }
  65.     }
  66.  
  67.     cnt[c]--;
  68. }
  69.  
  70. void f1(string s, int len, int x, int c, int k) {
  71.     if(len > x) return;
  72.     if(len == x) {
  73.         do {
  74.             res++;
  75.             if(res == k) return;
  76.         } while(next_permutation(s.begin(), s.end()));
  77.         cnt[c]--;
  78.         return;
  79.     }
  80.  
  81.     for(int i = max(1, c); i <= 26; i++) {
  82.         if(cnt[i] < a[i]) {
  83.             cnt[i]++;
  84.             f1(s + (char)(i + 'a' - 1), len + 1, x, i, k);
  85.             if(res == k) return;
  86.         }
  87.     }
  88.  
  89.     cnt[c]--;
  90. }
  91.  
  92. void solve(int x, int y, int k, int id) {
  93.    
  94.     bool okk = true;
  95.     for(int i = 1; i <= 26; i++) {
  96.         scanf("%d", &a[i]), a[i] = min(a[i], y);
  97.         if(a[i] < 0) {
  98.             okk = false;
  99.         }
  100.     }
  101.  
  102.     if(!okk) {
  103.         printf("NO\n");
  104.         return;
  105.     }
  106.     for(int i = 1; i <= 26; i++) cnt[i] = 0;
  107.  
  108.     res = 0;
  109.     for(int i = x; i <= y; i++) {
  110.         string s = "";
  111.         if(res == k) break;
  112.         f1(s, 0, i, 0, k);
  113.         for(int j = 1; j <= 26; j++) cnt[j] = 0;
  114.         if(res == k) break;
  115.     }
  116.  
  117.     if(res < k) {
  118.         printf("NO\n");
  119.         return;
  120.     } else {
  121.         printf("YES\n");
  122.     }
  123.  
  124.     for(int i = 1; i <= 26; i++) cnt[i] = 0;
  125.     res = 0;
  126.     for(int i = x; i <= y; i++) {
  127.         string s = "";
  128.         f(s, 0, i, 0, k);
  129.         for(int j = 1; j <= 26; j++) cnt[j] = 0;
  130.         if(res == k) break;
  131.     }
  132.     printf("\n");
  133. }
  134.  
  135. int main()
  136. {
  137.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  138.     #ifndef ONLINE_JUDGE
  139.     freopen("input.txt", "r", stdin);
  140.     freopen("output.txt", "w", stdout);
  141.     #else
  142.     //online
  143.     freopen("string.inp", "r", stdin);
  144.     freopen("string.out", "w", stdout);
  145.     #endif
  146.  
  147.     int tc = 1, ddd = 0;
  148.     while(true) {
  149.         //cout << "Case #" << ddd << ": ";
  150.         int x = 0, y = 0, k = 0;
  151.         scanf("%d %d %d", &x, &y, &k);
  152.         if(!x) return 0;
  153.         solve(x, y, k, ddd);
  154.         ddd++;
  155.     }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement