fork download
copy 
  1. #include <vector>
  2. #include <cassert>
  3. #include <utility>
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <string>
  7. #include <tuple>
  8.  
  9. struct Interval {
  10.     int l, r;
  11.     int length() const { return r-l+1; }
  12. };
  13.  
  14. long long pow10[17], ones[17];
  15.  
  16. int getBestCount(int L, int R, int power, int logPower, int D) {
  17.     if(power == 1) {
  18.         if(L <= D && D <= R) {
  19.             return 1;
  20.         }else {
  21.             return 0;
  22.         }
  23.     }
  24.  
  25.     if(L == 0) {
  26.         int cnt = 0;
  27.         while(ones[cnt + 1] * D <= R) cnt += 1;
  28.         return cnt; 
  29.     }
  30.  
  31.     if(R == power - 1) {
  32.         int cnt = logPower, dep = 0;
  33.         while(L <= ones[cnt] * D + ones[dep] * 9 * pow10[cnt]) {
  34.             cnt -= 1;
  35.             dep += 1;
  36.         }
  37.         return cnt;
  38.     }
  39.  
  40.     const int L0 = L / power, R0 = R / power;
  41.     if(L0 == R0) {
  42.         int childCnt = getBestCount(L % power, R % power, power / 10, logPower - 1, D);
  43.         if(D == L0) childCnt ++;
  44.         return childCnt;
  45.     }
  46.  
  47.     int count = 0;
  48.     for(int digit = L0; digit <= R0; digit++) {
  49.         int childCount;
  50.         if(digit == L0) {
  51.             childCount = getBestCount(L % power, power - 1, power / 10, logPower - 1, D);
  52.         }else if(L0 < digit && digit < R0) {
  53.             childCount = logPower;
  54.         }else {
  55.             childCount = getBestCount(0, R % power, power / 10, logPower - 1, D);
  56.         }
  57.  
  58.         int nextCount = childCount + (digit == D ? 1 : 0);
  59.         if(nextCount < count) continue;
  60.  
  61.         if(nextCount > count) {
  62.             count = nextCount;
  63.         }
  64.     }
  65.  
  66.     return count;
  67. }
  68.  
  69. std::vector<Interval> genBestIntervals(int L, int R, int power, int logPower, int D) {
  70.     if(power == 1) {
  71.         if(L <= D && D <= R) {
  72.             return std::vector<Interval>(1, Interval{D, D});
  73.         }else {
  74.             return std::vector<Interval>(1, Interval{L, R});
  75.         }
  76.     }
  77.  
  78.     const int L0 = L / power, R0 = R / power;
  79.     if(L0 == R0) {
  80.         auto child = genBestIntervals(L % power, R % power, power / 10, logPower - 1, D);
  81.         if(L0 > 0) for(auto &intv : child) intv.l += L0 * power, intv.r += L0 * power;
  82.         return child;
  83.     }
  84.  
  85.     int count = getBestCount(L, R, power, logPower, D);
  86.     std::vector<Interval> intervals;
  87.     for(int digit = L0; digit <= R0; digit++) {
  88.         int childCount;
  89.         if(digit == L0) {
  90.             childCount = getBestCount(L % power, power - 1, power / 10, logPower - 1, D);
  91.         }else if(L0 < digit && digit < R0) {
  92.             childCount = logPower;
  93.         }else {
  94.             childCount = getBestCount(0, R % power, power / 10, logPower - 1, D);
  95.         }
  96.  
  97.         int nextCount = childCount + (digit == D ? 1 : 0);
  98.         if(nextCount < count) continue;
  99.         assert(nextCount == count);
  100.  
  101.         std::vector<Interval> childIntervals;
  102.         if(digit == L0) {
  103.             childIntervals = genBestIntervals(L % power, power - 1, power / 10, logPower - 1, D);
  104.         }else if(L0 < digit && digit < R0) {
  105.             childIntervals.push_back({(power - 1) / 9 * D, (power - 1) / 9 * D});
  106.         }else {
  107.             childIntervals = genBestIntervals(0, R % power, power / 10, logPower - 1, D);
  108.         }
  109.  
  110.         for(Interval intv : childIntervals) {
  111.             intv.l += digit * power;
  112.             intv.r += digit * power;
  113.             intervals.push_back(intv);
  114.         }
  115.     }
  116.  
  117.     return intervals;
  118. }
  119.  
  120. struct Event {
  121.     int number, who, inserted;
  122. };
  123.  
  124. int main() {
  125. #ifdef IN_MY_COMPUTER
  126.     freopen("example.in.txt", "r", stdin);
  127. #endif
  128.     pow10[0] = 1;
  129.     for(int i = 1; i < 17; i++) pow10[i] = pow10[i-1] * 10, ones[i] = ones[i-1] * 10 + 1;
  130.  
  131.     int T; scanf("%d", &T);
  132.     for(int tc = 1; tc <= T; tc++) {
  133.         int A, B, C, D; scanf("%d%d%d%d", &A,&B,&C,&D);
  134.  
  135.         int logPower = std::to_string(B).length() - 1;
  136.         int power = 1; for(int rep = 0; rep < logPower; rep++) power *= 10;
  137.  
  138.         auto CIntervals = genBestIntervals(A, B, power, logPower, C);
  139.         auto DIntervals = genBestIntervals(A, B, power, logPower, D);
  140.  
  141.         std::vector<Event> events;
  142.         for(auto it : CIntervals) events.push_back({it.l, 0, +1}), events.push_back({it.r+1, 0, -1});
  143.         for(auto it : DIntervals) events.push_back({it.l, 1, +1}), events.push_back({it.r+1, 1, -1});
  144.         std::sort(events.begin(), events.end(), [&](const Event &e1, const Event &e2) { return e1.number < e2.number; });
  145.         events.push_back({B+1, -1, -1});
  146.  
  147.         int bestAnswer = -1;
  148.         long long bestProbability = -1;
  149.  
  150.         auto updateAnswer = [&bestAnswer, &bestProbability](int pos, long long prob) {
  151.             if(prob > bestProbability) {
  152.                 bestProbability = prob;
  153.                 bestAnswer = pos;
  154.             }else if(prob == bestProbability && bestAnswer > pos) {
  155.                 bestAnswer = pos;
  156.             }
  157.         };
  158.  
  159.  
  160.         long long totalLength[] = {0, 0};
  161.         for(auto &it : CIntervals) totalLength[0] += it.length();
  162.         for(auto &it : DIntervals) totalLength[1] += it.length();
  163.  
  164.         int alive[] = {0, 0};
  165.         long long totalCommonCases = 0;
  166.         for(size_t _idx = 0; _idx+1 < events.size(); _idx++) {
  167.             Event &current = events[_idx];
  168.             Event &next = events[_idx+1];
  169.  
  170.             alive[current.who] = alive[current.who] + current.inserted;
  171.             if(current.number < next.number || next.who < 0) {
  172.                 if(alive[0] > 0 && alive[1] > 0) {
  173.                     totalCommonCases += next.number - current.number;
  174.                 }
  175.             }
  176.         }
  177.  
  178.         alive[0] = 0;
  179.         alive[1] = 0;
  180.  
  181.         long long leftLength[] = {0, 0};
  182.         long long rightLength[] = {totalLength[0], totalLength[1]};
  183.  
  184.         for(size_t _idx = 0; _idx+1 < events.size(); _idx++) {
  185.             Event &current = events[_idx];
  186.             Event &next = events[_idx+1];
  187.  
  188.             alive[current.who] = alive[current.who] + current.inserted;
  189.             if(current.number < next.number || next.who < 0) {
  190.                 const long long length = (next.number - current.number);
  191.  
  192.                 for(int i= 0; i < 2; i++) {
  193.                     if(alive[i] > 0) rightLength[i] = rightLength[i] - length;
  194.                 }
  195.  
  196.                 // [5, 8) length=3
  197.                 // 5, 6 (7)
  198.                 // (5) 6 7
  199.                 auto update = [&](int x) {
  200.                     long long prob =
  201.                         3 * (leftLength[0] + x * alive[0]) * (rightLength[1] + (length - 1 - x) * alive[1]) +
  202.                         3 * (leftLength[1] + x * alive[1]) * (rightLength[0] + (length - 1 - x) * alive[0]);
  203.                     prob += 1 * totalCommonCases;
  204.                     if(alive[0] == 1) {
  205.                         prob += 1 * 1 * totalLength[1];
  206.                     }
  207.                     if(alive[1] == 1) {
  208.                         prob += 1 * totalLength[0] * 1;
  209.                     }
  210.                     if(alive[0] == 1 && alive[1] == 1) {
  211.                         prob -= 2 * 1 * 1 * 1;
  212.                     }
  213.                     updateAnswer(current.number + x, prob);
  214.                     return prob;
  215.                 };
  216.  
  217.                 update(0);
  218.                 update(length - 1);
  219.                 {
  220.                     int low = 0;
  221.                     int high = length - 1;
  222.                     while(high - low > 3) {
  223.                         int mid = (low + high) / 2;
  224.                         if(update(mid) > update(mid+1)) {
  225.                             high = mid;
  226.                         }else {
  227.                             low = mid;
  228.                         }
  229.                     }
  230.                     for(int x = low; x <= high; x++) {
  231.                         update(x);
  232.                     }
  233.                 }
  234.  
  235.                 for(int i= 0; i < 2; i++) {
  236.                     if(alive[i] > 0) leftLength[i] = leftLength[i] + length;
  237.                 }
  238.             }
  239.         }
  240.  
  241.         printf("%d\n", bestAnswer);
  242.  
  243.     }
  244.  
  245.     return 0;
  246. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vSV3Ap
language:
C++14 (gcc 8.3)
created:
4 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!