Advertisement
math2do

B - Candy Love (BIT2B)

Sep 21st, 2019
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename A, typename B>
  6. string to_string(pair<A, B> p);
  7.  
  8. template <typename A, typename B, typename C>
  9. string to_string(tuple<A, B, C> p);
  10.  
  11. template <typename A, typename B, typename C, typename D>
  12. string to_string(tuple<A, B, C, D> p);
  13.  
  14. string to_string(const string& s) {
  15.   return '"' + s + '"';
  16. }
  17.  
  18. string to_string(const char* s) {
  19.   return to_string((string) s);
  20. }
  21.  
  22. string to_string(bool b) {
  23.   return (b ? "true" : "false");
  24. }
  25. string to_string(const char &ch) {
  26.   return string(1, ch);
  27. }
  28.  
  29. string to_string(vector<bool> v) {
  30.   bool first = true;
  31.   string res = "{";
  32.   for (int i = 0; i < static_cast<int>(v.size()); i++) {
  33.     if (!first) {
  34.       res += ", ";
  35.     }
  36.     first = false;
  37.     res += to_string(v[i]);
  38.   }
  39.   res += "}";
  40.   return res;
  41. }
  42.  
  43. template <size_t N>
  44. string to_string(bitset<N> v) {
  45.   string res = "";
  46.   for (size_t i = 0; i < N; i++) {
  47.     res += static_cast<char>('0' + v[i]);
  48.   }
  49.   return res;
  50. }
  51.  
  52. template <typename A>
  53. string to_string(A v) {
  54.   bool first = true;
  55.   string res = "{";
  56.   for (const auto &x : v) {
  57.     if (!first) {
  58.       res += ", ";
  59.     }
  60.     first = false;
  61.     res += to_string(x);
  62.   }
  63.   res += "}";
  64.   return res;
  65. }
  66.  
  67. template <typename A, typename B>
  68. string to_string(pair<A, B> p) {
  69.   return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
  70. }
  71.  
  72. template <typename A, typename B, typename C>
  73. string to_string(tuple<A, B, C> p) {
  74.   return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
  75. }
  76.  
  77. template <typename A, typename B, typename C, typename D>
  78. string to_string(tuple<A, B, C, D> p) {
  79.   return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
  80. }
  81.  
  82. void debug_out() { cerr << endl; }
  83.  
  84. template <typename Head, typename... Tail>
  85. void debug_out(Head H, Tail... T) {
  86.   cerr << " " << to_string(H);
  87.   debug_out(T...);
  88. }
  89.  
  90. #ifdef LOCAL
  91. #define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  92. #else
  93. #define pr(...) 42
  94. #endif
  95.  
  96. double tick(){
  97.   static clock_t oldtick;
  98.   clock_t newtick = clock();
  99.   double diff = 1.0 * (newtick - oldtick) / CLOCKS_PER_SEC;
  100.   oldtick = newtick;
  101.   return diff;
  102. }
  103.  
  104. int main() {
  105.   ios_base::sync_with_stdio(false);
  106.   cin.tie(NULL);
  107.   cout << setprecision(10);
  108.   cout << fixed;
  109.   #ifdef LOCAL
  110.     freopen("b_candy_love.in", "rt", stdin);
  111.   #endif
  112.  
  113.  
  114.   int tt, x;
  115.   cin >> tt;
  116.   while(tt--) {
  117.     int n;
  118.     cin >> n;
  119.     vector <int> arr(n);
  120.     for (int i = 0; i < n; i++) {
  121.       cin >> arr[i];
  122.     }
  123.     cin >> x;
  124.  
  125.     vector <long long> cum1(n, 0);
  126.     vector <long long> cum2(n, 0);
  127.     cum1[0] = arr[0];
  128.     for (int i = 1; i < n; i++) {
  129.       cum1[i] = cum1[i - 1] + arr[i];
  130.     }
  131.     cum2[n - 1] = arr[n - 1];
  132.     for (int i = n - 2; i >= 0; i--) {
  133.       cum2[i] = cum2[i + 1] + arr[i];
  134.     }
  135.    
  136.     if (n == 1) cout << 1 << " " << 0 << endl;
  137.     else if (n == 2) cout << 1 << " " << 1 << endl;
  138.     else {
  139.       pair <int, int> ans = {1, 1};
  140.       for (int i = 1; i < n - 1; i++) {
  141.         long long tl = cum1[i - 1] / x;
  142.         long long rl = cum2[i + 1];
  143.         if (tl == rl) {
  144.           if (cum1[i - 1] % x == 0) {
  145.             ans.first = i + 1;
  146.             ans.second = n - i - 1;
  147.           } else {
  148.             ans.first = i;
  149.             ans.second = n - i;  
  150.           }
  151.           break;
  152.         }
  153.         else if (tl < rl) {
  154.           ans.first = i + 1;
  155.           ans.second = n - i - 1;
  156.         } else {
  157.           ans.first = i;
  158.           ans.second = n - i;
  159.           break;
  160.         }
  161.       }
  162.       cout << ans.first << " " << ans.second << endl;
  163.     }
  164.   }
  165.   #ifdef LOCAL
  166.     fprintf(stderr, "Time elapsed: %.12lf secs...\n", tick());
  167.   #endif
  168.   return 0;
  169. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement