Advertisement
mitkonikov

Untitled

Feb 23rd, 2020
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> segments;
  6. char chars[10001];
  7.  
  8. map<  pair<int, pair<int, int>  >, char  > memo;
  9. char EMPTY;
  10.  
  11. bool rec(int segment, int b, int c) {
  12.     if (segment > segments.size() - 1) return true;
  13.  
  14.     double half = (double)segments[segment] / 2;
  15.  
  16.     /*cout << "one rec call : " << endl;
  17.     cout << "segment length: " << segments[segment] << endl;;
  18.     cout << b << " - " << c << " : " << floor(half) << ", " << ceil(half) << endl;*/
  19.  
  20.     int nextB = b - ceil(half);
  21.     int nextC = c - floor(half);
  22.  
  23.     if (nextB >= 0 && nextC >= 0) {
  24.         char nextMemo = memo[make_pair(segment+1, make_pair(nextB, nextC))];
  25.         if (nextMemo != EMPTY) {
  26.             if (nextMemo == 'b') {
  27.                 chars[segment] = 'B';
  28.                 return true;
  29.             }
  30.         } else {
  31.             if (rec(segment+1, nextB, nextC)) {
  32.                 chars[segment] = 'B';
  33.                 memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'b';
  34.                 return true;
  35.             } else {
  36.                 memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'f';
  37.             }
  38.         }
  39.     }
  40.  
  41.     nextB = b - floor(half);
  42.     nextC = c - ceil(half);
  43.  
  44.     if (nextB >= 0 && nextC >= 0) {
  45.         char nextMemo = memo[make_pair(segment+1, make_pair(nextB, nextC))];
  46.         if (nextMemo != EMPTY) {
  47.             if (nextMemo == 'c') {
  48.                 chars[segment] = 'C';
  49.                 return true;
  50.             }
  51.         } else {
  52.             if (rec(segment+1, nextB, nextC)) {
  53.                 chars[segment] = 'C';
  54.                 memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'c';
  55.                 return true;
  56.             } else {
  57.                 memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'f';
  58.             }
  59.         }
  60.     }
  61.  
  62.     return false;
  63. }
  64.  
  65.  
  66. int main()
  67. {
  68.     int a, b, c;
  69.     cin >> a >> b >> c;
  70.  
  71.     int sum = a+b+c;
  72.  
  73.     char dp[sum];
  74.  
  75.     for (int i = 0; i < sum; ++i) {
  76.         dp[i] = '0';
  77.     }
  78.  
  79.     int previousA =0;
  80.     for (int i = 0; i < a; ++i) {
  81.         int currentA;
  82.         cin >> currentA;
  83.  
  84.         dp[currentA - 1] = 'A';
  85.  
  86.         int diff = currentA - previousA - 1;
  87.  
  88.         if (diff != 0)
  89.             segments.push_back(currentA - previousA - 1);
  90.  
  91.         previousA = currentA;
  92.     }
  93.  
  94.     int diff = sum - previousA;
  95.  
  96.     if (diff != 0)
  97.         segments.push_back(diff);
  98.  
  99.     /*for (int i = 0; i < segments.size(); ++i) {
  100.         cout << i << "th segment: " << segments[i] << "-" << chars[i] << endl;
  101.     }*/
  102.  
  103.     if (rec(0, b, c) == false) {
  104.         cout << -1 << endl;
  105.         return 0;
  106.     }
  107.  
  108.  
  109.     int currentSegment = 0;
  110.     for (int i = 0; i < sum;) {
  111.         if (dp[i] == 'A') {
  112.             cout << 'A';
  113.             i++;
  114.         } else {
  115.             char firstChar = chars[currentSegment];
  116.  
  117.             for (int k = 0; k < segments[currentSegment]; ++k) {
  118.                 if (firstChar == 'B') {
  119.                     cout << 'B';
  120.                     firstChar = 'C';
  121.                 } else if (firstChar == 'C') {
  122.                     cout << 'C';
  123.                     firstChar = 'B';
  124.                 }
  125.             }
  126.  
  127.             i += segments[currentSegment];
  128.  
  129.             if (currentSegment < segments.size() - 1)
  130.                 currentSegment++;
  131.         }
  132.     }
  133.  
  134.     cout << endl;
  135.  
  136.     return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement