Raslboyy

588

Dec 4th, 2019
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <algorithm>
  5. #include <string>
  6. #include <math.h>
  7. #include <climits>
  8. #include <unordered_set>
  9.  
  10. //#include <chrono>
  11. //#include <fstream>
  12. //#include <bits/stdc++.h>
  13.  
  14. #define mp make_pair
  15. #define pb push_back
  16. #define eb emplace_back
  17. #define x first
  18. #define y second
  19. #define sz(x) (int)x.size()
  20. #define all(x) begin(x), end(x)
  21. #define rall(x) rbegin(x), rend(x)
  22. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  23. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  24.  
  25. using namespace std;
  26.  
  27. typedef unsigned long long ull;
  28. typedef long long ll;
  29. typedef long double ld;
  30. typedef pair<int, int> pi;
  31. typedef pair<ll, ll> pl;
  32. typedef vector<int> veci;
  33. typedef vector<bool> vecb;
  34. typedef vector<vector<int>> vvi;
  35. typedef vector<vector<bool>> vvb;
  36.  
  37. const int INF_I = 1e9;
  38. const ll INF_LL = 1e18;
  39.  
  40. vector<unordered_set<int>> vec;
  41. vector<bool> used;
  42. vector<int> p;
  43.  
  44. bool dfs(int v) {
  45.     if (used[v])
  46.         return false;
  47.     used[v] = true;
  48.     for (int i : vec[v])
  49.         if (p[i] == -1 || dfs(p[i])) {
  50.             p[i] = v;
  51.             return true;
  52.         }
  53.     return false;
  54. }
  55.  
  56. int main() {
  57.     /*ifstream cin("in.txt");
  58.     ofstream cout("out.txt");
  59.     auto start_time = chrono::high_resolution_clock::now();*/
  60.  
  61.     ios::sync_with_stdio(false);
  62.     cin.tie(0);
  63.     cout.tie(0);
  64.  
  65.    
  66.     int n;
  67.     cin >> n;
  68.     string tem;
  69.     cin >> tem;
  70.     int len = tem.size();
  71.     if (n < len) {
  72.         cout << "NO\n";
  73.         return 0;
  74.     }
  75.  
  76.     p.assign(n, -1);
  77.  
  78.     vector<list<int>> vec_ch(26);
  79.     for (int i = 0; i < len; i++)
  80.         vec_ch[tem[i] - 'A'].eb(i);
  81.     vec.assign(len, unordered_set<int>());
  82.  
  83.  
  84.     for (int i = 0; i < n; i++)
  85.         for (int j = 0; j < 6; j++) {
  86.             char ch;
  87.             cin >> ch;
  88.             for (int cur : vec_ch[ch - 'A'])
  89.                 vec[cur].emplace(i);
  90.         }
  91.     int cnt = 0;
  92.     for (int i = 0; i < n; i++) {
  93.         used.assign(len, 0);
  94.         cnt += (int)dfs(i);
  95.     }
  96.  
  97.     if (cnt < len) {
  98.         cout << "NO\n";
  99.         return 0;
  100.     }
  101.     cout << "YES\n";
  102.     vector<int> res(len);
  103.     for (int i = 0; i < n; i++)
  104.         res[p[i]] = i + 1;
  105.    
  106.     for (int i : res)
  107.         cout << i << " ";
  108.  
  109.     /*auto end_time = chrono::high_resolution_clock::now();
  110.     chrono::duration<double> duration = end_time - start_time;
  111.     cout << duration.count() << "\n";
  112.     cin.close();
  113.     cout.close();*/
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment