Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> segments;
- char chars[10001];
- map< pair<int, pair<int, int> >, char > memo;
- char EMPTY;
- bool rec(int segment, int b, int c) {
- if (segment > segments.size() - 1) return true;
- double half = (double)segments[segment] / 2;
- /*cout << "one rec call : " << endl;
- cout << "segment length: " << segments[segment] << endl;;
- cout << b << " - " << c << " : " << floor(half) << ", " << ceil(half) << endl;*/
- int nextB = b - ceil(half);
- int nextC = c - floor(half);
- if (nextB >= 0 && nextC >= 0) {
- char nextMemo = memo[make_pair(segment+1, make_pair(nextB, nextC))];
- if (nextMemo != EMPTY) {
- if (nextMemo == 'b') {
- chars[segment] = 'B';
- return true;
- }
- } else {
- if (rec(segment+1, nextB, nextC)) {
- chars[segment] = 'B';
- memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'b';
- return true;
- } else {
- memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'f';
- }
- }
- }
- nextB = b - floor(half);
- nextC = c - ceil(half);
- if (nextB >= 0 && nextC >= 0) {
- char nextMemo = memo[make_pair(segment+1, make_pair(nextB, nextC))];
- if (nextMemo != EMPTY) {
- if (nextMemo == 'c') {
- chars[segment] = 'C';
- return true;
- }
- } else {
- if (rec(segment+1, nextB, nextC)) {
- chars[segment] = 'C';
- memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'c';
- return true;
- } else {
- memo[make_pair(segment+1, make_pair(nextB, nextC))] = 'f';
- }
- }
- }
- return false;
- }
- int main()
- {
- int a, b, c;
- cin >> a >> b >> c;
- int sum = a+b+c;
- char dp[sum];
- for (int i = 0; i < sum; ++i) {
- dp[i] = '0';
- }
- int previousA =0;
- for (int i = 0; i < a; ++i) {
- int currentA;
- cin >> currentA;
- dp[currentA - 1] = 'A';
- int diff = currentA - previousA - 1;
- if (diff != 0)
- segments.push_back(currentA - previousA - 1);
- previousA = currentA;
- }
- int diff = sum - previousA;
- if (diff != 0)
- segments.push_back(diff);
- /*for (int i = 0; i < segments.size(); ++i) {
- cout << i << "th segment: " << segments[i] << "-" << chars[i] << endl;
- }*/
- if (rec(0, b, c) == false) {
- cout << -1 << endl;
- return 0;
- }
- int currentSegment = 0;
- for (int i = 0; i < sum;) {
- if (dp[i] == 'A') {
- cout << 'A';
- i++;
- } else {
- char firstChar = chars[currentSegment];
- for (int k = 0; k < segments[currentSegment]; ++k) {
- if (firstChar == 'B') {
- cout << 'B';
- firstChar = 'C';
- } else if (firstChar == 'C') {
- cout << 'C';
- firstChar = 'B';
- }
- }
- i += segments[currentSegment];
- if (currentSegment < segments.size() - 1)
- currentSegment++;
- }
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement