Korotkodul

CF D 4 ошибка исполнения тест 2

Aug 1st, 2022
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17.     for (auto x: v) cout<<x<<' ';
  18.     cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22.     for (auto x: v) cout<<x<<' ';
  23.     cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28.     for (auto x: v) cv(x);
  29.     cout<<"\n";
  30. }
  31.  
  32. void cvb(vector <bool> v){
  33.     for (bool x: v) cout<<x<<' ';
  34.     cout<<"\n";
  35. }
  36.  
  37. void cvs(vector <string>  v){
  38.     for (auto a: v){
  39.         cout<<a<<"\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a){
  44.     for (auto p: a){
  45.         cout<<p.first<<' '<<p.second<<"\n";
  46.     }
  47.     cout<<"\n";
  48. }
  49.  
  50. bool sh=0;
  51.  
  52. string t;
  53. int n;
  54. vector <string> sv;
  55.  
  56. struct in{
  57.     int fr,  ln,  ids;
  58. };
  59.  
  60. bool cmp(in a, in b){
  61.     return a.fr < b.fr || a.fr == b.fr && a.ln > b.ln;
  62. }
  63.  
  64. void slv(){
  65.  
  66.     cin>>t>>n;
  67.     sv.resize(n);
  68.     for (string &i: sv) cin>>i;
  69.     vector <in> al;
  70.  
  71.     if (sh){
  72.         cout<<"A\n";
  73.     }
  74.  
  75.     in x;
  76.     int id=-1;
  77.     for (string s: sv){
  78.         id++;
  79.  
  80.         if (sh){
  81.             //cout<<"id s = "<<id<<' '<<s<<"\n";
  82.         }
  83.  
  84.         for (int i = 0; i <= t.size() - s.size(); ++i){
  85.             if (t.substr(i, s.size()) == s){
  86.  
  87.                 if (sh){
  88.                     //cout<<"found\n";
  89.                 }
  90.  
  91.                 x = {i, s.size(), id};
  92.                 al.push_back(x);
  93.             }
  94.         }
  95.     }
  96.     /*
  97. abacabaca
  98. 3
  99. aba
  100. bac
  101. aca
  102.  
  103.  
  104. */
  105.  
  106.     sort(al.begin(), al.end(), cmp);
  107.     if (al.empty()){
  108.         cout<<-1<<"\n";
  109.         return;
  110.     }
  111.     int from=0,to=0;
  112.     vector <pii> ans;//опследовательность жадных ходов
  113.     id=0;//ЖАДНОСТЬ
  114.     bool can=1;
  115.     pii mv; // move
  116.  
  117.     if (sh){
  118.         cout<<"B\n";
  119.         cout<<"al.size() = "<<al.size()<<"\n";
  120.         cout<<"al\n";
  121.         for (auto p: al){
  122.             cout<<p.fr<<' '<<p.ln<<' '<<p.ids<<"\n";
  123.         }
  124.     }
  125.  
  126.     while (from < t.size() && to < t.size()){
  127.         vector <pii> now; //{длина за зоной изведанного, id из al}
  128.         //id = from;
  129.  
  130.         if (sh){
  131.             cout<<"from  to = "<<from<<' '<<to<<"\n";
  132.         }
  133.  
  134.         while (id < al.size() && al[id].fr <= to){
  135.             now.push_back({al[id].fr + al[id].ln - 1 - (to - 1), id});
  136.  
  137.             if (sh){
  138.                     cout<<"id = "<<id<<"\n";
  139.             }
  140.  
  141.             id++;
  142.         }
  143.  
  144.  
  145.         sort(now.begin(), now.end());
  146.         reverse(now.begin(), now.end());
  147.  
  148.         if (sh){
  149.             //cout<<"C\n";
  150.  
  151.             cout<<"now\n";
  152.             cvp(now);
  153.             if (sh){
  154.                 cout<<"ans\n";
  155.                 cvp(ans);
  156.             }
  157.         }
  158.  
  159.         //берем первый
  160.         if (now.empty() || !now.empty() && now[0].first <= 0){//значит не переплюнули границу неизведанного
  161.             can=0;
  162.             break;
  163.         }
  164.         in gd = al[now[0].second];
  165.         to = gd.fr + gd.ln;
  166.         mv = {gd.ids, gd.fr};
  167.         ans.push_back(mv);
  168.         from++;
  169.     }
  170.  
  171.     if (sh){
  172.         cout<<"id = "<<id<<"\n";
  173.         cout<<"NIGGER ASS FUCK\n";
  174.     }
  175.  
  176.     if (!can){
  177.         cout<<-1<<"\n";
  178.         return;
  179.     }
  180.  
  181.     cout<<ans.size()<<"\n";
  182.     for (auto p: ans){
  183.         cout<<(p.first+1)<<' '<<(p.second+1)<<"\n";
  184.     }
  185. }
  186.  
  187. /*
  188. На 2м тесте все вылетает -- проверь, а на 1м WA
  189. */
  190. /*
  191. abacabaca
  192. 3
  193. aba
  194. bac
  195. aca
  196.  
  197. */
  198. int main()
  199. {
  200.     ios::sync_with_stdio(0);
  201.     cin.tie(0);
  202.     cout.tie(0);
  203.     int q=1;
  204.     if (!sh) cin>>q;
  205.     for (int go=0;go<q;++go){
  206.         slv();
  207.     }
  208. }
  209.  
Add Comment
Please, Sign In to add comment