fork download
copy 
  1. /*
  2. Author : deepak2015
  3. Plagiarism is bad.
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define MOD 1000000007
  9. #define epsilon 0.000000000001
  10. #define PI 3.1415926535897932
  11. #define I_MAX 92203685477580799
  12. #define I_MIN -92203685477580799
  13. #define ll long long
  14. #define endl "\n"
  15.  
  16. #define mset(arr,x) memset(arr,x,sizeof(arr))
  17. #define rep(i,s,e) for(i=s;i<=e;i++)
  18. #define rrep(i,s,e) for(i=s;i>=e;i--)
  19. #define min(a,b) ((a)<(b)?(a):(b))
  20. #define max(a,b) ((a)>(b)?(a):(b))
  21.  
  22. // Useful STL commands:
  23. #define pb push_back
  24. #define mp make_pair
  25. #define f first
  26. #define s second
  27. #define all(c) c.begin(),c.end()
  28. #define tr(c,it) for(auto it=c.begin();it!=c.end();++it)
  29. #define trrev(c,it) for(auto it=c.rbegin();it!=c.rend();++it)
  30.  
  31. #define DEBUG
  32. #ifdef DEBUG
  33. #define trace1(x)                    cerr << #x << ": " << x << endl;
  34. #define trace2(x, y)                 cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  35. #define trace3(x, y, z)              cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  36. #define trace4(a, b, c, d)           cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  37. #define trace5(a, b, c, d, e)        cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  38. #define trace6(a, b, c, d, e, f)     cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  39. #else
  40. #define trace1(x)
  41. #define trace2(x, y)
  42. #define trace3(x, y, z)
  43. #define trace4(a, b, c, d)
  44. #define trace5(a, b, c, d, e)
  45. #define trace6(a, b, c, d, e, f)
  46. #endif
  47.  
  48. // scanf and printf
  49. #define si(a)			scanf("%d", &a)
  50. #define sl(a)			scanf("%lld", &a)
  51. #define pi(a)			printf("%d", a)
  52. #define pl(a)			printf("%lld", a)
  53. #define pn 				printf("\n")
  54.  
  55. ll gcd(ll a, ll b)
  56. {
  57.     if( (a == 0) || (b == 0) )
  58.         return a + b;
  59.  
  60.     return gcd(b, a % b);
  61. }
  62. ll pow_mod(ll a, ll b)
  63. {
  64.     ll res = 1;
  65.     while(b)
  66.     {
  67.         if(b & 1)
  68.             res = (res * a)%MOD;
  69.         a = (a * a)%MOD;
  70.         b >>= 1;
  71.     }
  72.  
  73.     return (res%MOD);
  74. }
  75. ll pow_2(ll a, ll b)
  76. {
  77.     ll res = 1;
  78.     while(b)
  79.     {
  80.         if(b & 1)
  81.             res = (res * a);
  82.         a = (a * a);
  83.         b >>= 1;
  84.     }
  85.     return res;
  86. }
  87. bool isPrime(ll a)
  88. {
  89.     for(int i=3; (i*i)<=a; i+=2)
  90.     {
  91.         if( (a%i)==0 )
  92.             return false;
  93.     }
  94.     if( ( a!=2 ) && ( (a%2)==0 ) )
  95.         return false;
  96.     if( a==1 )
  97.         return false;
  98.  
  99.     return true;
  100. }
  101. string con_ll_to_str( int a )
  102. {
  103.     stringstream mystr;
  104.     mystr << a;
  105.     return mystr.str();
  106. }
  107. ll con_str_to_ll( string st )
  108. {
  109.     ll numb = 0;
  110.     int len = st.size(), i, j = 0;
  111.     rrep(i, len-1, 0)
  112.     {
  113.        numb += ( pow_2(10, j) * ( st[i] - '0' ) );
  114.        j++;
  115.     }
  116.  
  117.     return numb;
  118. }
  119. ll baseno_to_decimal( string st, ll basee )
  120. {
  121.     ll i = 0, j, anss = 0;
  122.     rrep(j, (int)st.length()-1, 0)
  123.     {
  124.         anss += ( st[j] - '0' ) * pow_2( basee, i );
  125.         i++;
  126.     }
  127.  
  128.     return anss;
  129. }
  130. string decimal_to_string( ll num, ll basee )
  131. {
  132.     ll i = 0, j, opop;
  133.     string anss = "";
  134.     vector< string > stri;
  135.     stri.pb("0"); stri.pb("1"); stri.pb("2"); stri.pb("3");
  136.     stri.pb("4"); stri.pb("5"); stri.pb("6"); stri.pb("7");
  137.     stri.pb("8"); stri.pb("9"); stri.pb("A"); stri.pb("B");
  138.     stri.pb("C"); stri.pb("D"); stri.pb("E"); stri.pb("F");
  139.     if( num==0 )
  140.     {
  141.         return "0";
  142.     }
  143.     while( num )
  144.     {
  145.         opop = num%basee;
  146.         anss += stri[opop];
  147.         num /= basee;
  148.     }
  149.     reverse( all(anss) );
  150.  
  151.     return anss;
  152. }
  153. const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
  154. const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
  155. // Always use double and never float.
  156. // map : log2(N) find, count, etc
  157. /*
  158. struct comp
  159. {
  160.     inline bool operator()(const pair<pair<ll, int>, bool>& pa1, const pair<pair<ll, int>, bool>& pa2) const
  161.     {
  162.         if (pa1.f.f == pa2.f.f)
  163.             return pa1.f.s < pa2.f.s;
  164.         return pa1.f.f < pa2.f.f;
  165.     }
  166. };
  167. */
  168. // bitset<99999000000000>& c = *(new bitset<99999000000000>());   // For O(1) lookup the max bitset space required.
  169. // Don't use map in qsort comp, instead store value in vector in form of pair. It is because it takes n*log(n)*log(n) time that increases the complexity.
  170. // cout << fixed << setprecision(12) << ans;  // For 12 decimal places after the number.
  171. // vector iterators can only be compared.
  172. // For Directed Acyclic Graph, DFS without marking visited vertices could lead to TLE( exponential solution ).
  173.  
  174. int F[1000010], S[1000010], arr[10000010];
  175. set<int> se;
  176. vector< int > resf;
  177. int main()
  178. {
  179.  
  180. //     ios_base::sync_with_stdio(false);
  181. //     cin.tie(0);
  182.  
  183.      int T, N, M, K, i, j, maa = INT_MIN;
  184.      string st;
  185.  
  186.      cin >> N >> M >> K;
  187.      rep(i, 1, N)
  188.      {
  189.          scanf("%d", &F[i]);
  190.          maa = max(maa, F[i]);
  191.      }
  192.      rep(i, 1, M)
  193.      {
  194.          scanf("%d", &S[i]);
  195.          maa = max(maa, S[i]);
  196.      }
  197.      //trace1(maa)
  198.      rep(i, 0, maa)
  199.      {
  200.         se.insert( i );
  201.         arr[i] = K;
  202.      }
  203.  
  204.      rep(i, 1, N)
  205.      {
  206.          if( se.size() && *se.begin() <= F[i] )
  207.          {
  208.              auto it = se.upper_bound( F[i] );
  209.              it--;
  210.              arr[*it]--;
  211.              if( arr[*it]==0 )
  212.              {
  213.                  se.erase( it );
  214.              }
  215.          }
  216.          else
  217.          {
  218.              printf("-1");
  219.              return 0;
  220.          }
  221.      }
  222.  
  223.      rep(i, 1, M)
  224.      {
  225.          if( se.size() && *se.begin() <= S[i] )
  226.          {
  227.              auto it = se.upper_bound( S[i] );
  228.              it--;
  229.              resf.pb(i);
  230.              arr[*it]--;
  231.              if( arr[*it]==0 )
  232.              {
  233.                  se.erase( it );
  234.              }
  235.          }
  236.      }
  237.      int opok = resf.size();
  238.      printf("%d\n", opok);
  239.      rep(i, 0, opok-1)
  240.      {
  241.          printf("%d ", resf[i]);
  242. //         cout << resf[i] << " ";
  243.      }
  244.  
  245.      return 0;
  246. }
  247.  
Success #stdin #stdout 0s 62120KB
comments (?)
stdin
copy 
2 1 2
0 1
0
stdout
copy 
1
1
https://ideone.com/Tdob4l
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!