fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define __builtin_ctz __builtin_ctzll
  17. #define __builtin_clz __builtin_clzll
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  21. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  22.   while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  23. }
  24. #ifdef LOCAL
  25. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  26. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  27. #else
  28. #define debug(...) (__VA_ARGS__)
  29. #define debugv(x)
  30. #define cerr if(0)cout
  31. #endif
  32. #define left ____left
  33. #define hash ____hash
  34. typedef long long ll;
  35. typedef long double LD;
  36. typedef pair<int, int> PII;
  37. typedef pair<ll, ll> PLL;
  38. typedef vector<int> VI;
  39. typedef vector<VI> VVI;
  40. typedef vector<ll> VLL;
  41. typedef vector<pair<int, int> > VPII;
  42. typedef vector<pair<ll, ll> > VPLL;
  43.  
  44. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  45. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  46. template<class T1, class T2>
  47. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  48. template<class A, class B, class C> struct Triple { A first; B second; C third;
  49.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  50. template<class T> void ResizeVec(T&, vector<int>) {}
  51. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  52.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  53.   for (T& v : vec) { ResizeVec(v, sz); }
  54. }
  55. typedef Triple<int, int, int> TIII;
  56. template<class A, class B, class C>
  57. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  58. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  59. template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  60. template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  61.  
  62. const int kInf = 1e18;
  63. const int N = 1e6 + 5;
  64. int a[N], b[N];
  65. int typ[N];
  66. int aktc, shift;
  67. vector<int> deactivated;
  68. int32_t main() {
  69.  
  70.   ios_base::sync_with_stdio(0);
  71.   cout << fixed << setprecision(10);
  72.   cerr << fixed << setprecision(10);
  73.   cin.tie(0);
  74.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  75.  
  76.   int n, k;
  77.   cin>>n>>k;
  78.   RE (i, n) {
  79.     cin>>a[i];
  80.   }
  81.   RE (i, n) {
  82.     cin>>b[i];
  83.   }
  84.   int cnt_a = 0;
  85.   RE (i, n) {
  86.     if (a[i] < b[i]) {
  87.       cnt_a++;
  88.       typ[i] = 1;
  89.     }
  90.   }
  91.   int swapped = 0;
  92.   if (cnt_a > k) {
  93.     cnt_a = n - cnt_a;
  94.     k = n - k;
  95.     RE (i, n) {
  96.       swap(a[i], b[i]);
  97.       typ[i] = 1 - typ[i];
  98.     }
  99.     swapped = 1;
  100.   }
  101.   debug(swapped, cnt_a, k);
  102.   int lbd = 0;
  103.   int bil = 0;
  104.   RE (i, n) {
  105.     bil += min(a[i], b[i]);
  106.     maxi(bil, 0ll);
  107.     maxi(lbd, bil);
  108.   }
  109.   int need_changed = k - cnt_a;
  110.   int kl = lbd, kp = kInf, faj = kInf;
  111.   string best;
  112.   while (kl <= kp) {
  113.     aktc = (kl + kp) / 2;
  114.     shift = 0;
  115.     VI bils{0};
  116.     deactivated.clear();
  117.     string here(n + 1, 'B');
  118.     set<PII> active;
  119.     int on_set = 0;
  120.     int fail = 0;
  121.     RE (i, n) {
  122.       if (typ[i] == 1) { // moje tansze
  123.         here[i] = 'A';
  124.         shift += a[i];
  125.       } else { // jego tansze
  126.         shift += b[i];
  127.         active.insert({a[i] - b[i], i});
  128.         on_set += a[i] - b[i];
  129.       }
  130.       while (shift < 0) {
  131.         if (active.empty()) {
  132.           shift = 0;
  133.           break;
  134.         }
  135.         auto it = active.begin();
  136.         if (shift + it->st <= 0) {
  137.           deactivated.PB(it->nd);
  138.           shift += it->st;
  139.           on_set -= it->st;
  140.           active.erase(active.begin());
  141.         } else {
  142.           PII p2 = *it;
  143.           p2.st += shift;
  144.           on_set += shift;
  145.           active.erase(active.begin());
  146.           active.insert(p2);
  147.           shift = 0;
  148.         }
  149.       }
  150.       while (shift + on_set > aktc) {
  151.         if (active.empty()) {
  152.           fail = 1;
  153.           break;
  154.         }
  155.         on_set -= prev(active.end())->st;
  156.         active.erase(prev(active.end()));
  157.       }
  158.     }
  159.     for (auto p : active) {
  160.       deactivated.PB(p.nd);
  161.     }
  162.     if (!fail && SZ(deactivated) >= need_changed) {
  163.       faj = aktc;
  164.       kp = aktc - 1;
  165.       REP (i, need_changed) {
  166.         here[deactivated[i]] = 'A';
  167.       }
  168.       best = here;
  169.     } else {
  170.       kl = aktc + 1;
  171.     }
  172.   }
  173.   cout<<faj<<endl;
  174.   if (swapped) {
  175.     RE (i, n) {
  176.       best[i] = ((best[i] + 1) ^ 1) - 1;
  177.       swap(a[i], b[i]);
  178.     }
  179.     k = n - k;
  180.   }
  181.   cout<<best.substr(1)<<"\n";
  182. #ifdef LOCAL
  183.   lbd = 0;
  184.   bil = 0;
  185.   int cnta = 0;
  186.   RE (i, n) {
  187.     if (best[i] == 'A') {
  188.       bil += a[i];
  189.       cnta++;
  190.     } else {
  191.       bil += b[i];
  192.     }
  193.     maxi(bil, 0ll);
  194.     maxi(lbd, bil);
  195.   }
  196.   assert(cnta == k);
  197.   assert(lbd == faj);
  198. #endif
  199.  
  200.   return 0;
  201. }
  202.  
Time limit exceeded #stdin #stdout 5s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CCvgl0
language:
C++14 (gcc 8.3)
created:
2 years 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!