Monistus

#include<iostream>
#include<bits/stdc++.h>
#include<string> 
#include<map>
#include <unordered_map>
using namespace std;
 
typedef long long ll;
 
constexpr ll M = 1000000007;
constexpr ll P = (1 << 18);
constexpr int INF = 1e9;
 
unordered_map<string, vector<char>> m;
string before; 
int seenCount;
int maxSize;
 
vector<char> solve(vector<char> input) {
	maxSize = max((int)input.size(), maxSize);
	//cout << maxSize << endl;

	string hash = "";
	if ((int)input.size() < 1000) {
		for (char ch : input) {
			hash += ch;
		}

		if (m.count(hash)) { //size limit?
			seenCount++;
			return m[hash];	
		}
	}
	

	for (int i=0; i<(int)input.size(); i++) {
		char ch = input[i];
		int digit = ch - '0'; 
 
		if (digit > 0 && digit <= 9) {
			//string b4 = input.substr(0, i); 
			//string expanded = input.substr(i+1, digit); 
			//string after = input.substr(i+1); 

			vector<char> before(input.begin(), input.begin()+i);
			vector<char> expanded(input.begin()+i+1, input.begin()+i+1+digit);
			vector<char> after(input.begin() + i + 1, input.end()); 

 
			//if (m.count(expanded)) {
			//	seenCount++;
			//	return m[expanded] + solve(after);
			//}

			bool overlaps = false;
			int s = (int) expanded.size();
			for (int j=0; j<s; j++) {
				char ch = expanded[j];
				int d = ch - '0'; 
				if (d > 0 && d <= 9) {
					if (j + d >= s) {
						overlaps = true;
						break;
					}
				}
			}

			//cout << s << " " << overlaps << endl;

			//overlaps = true;
			vector<char> ans;

			if (overlaps) {
				expanded.insert(expanded.end(), after.begin(), after.end());
				ans = solve(expanded);	
			} else {
				ans = solve(expanded);
				vector<char> s2 = solve(after);
				ans.insert(ans.end(), s2.begin(), s2.end());
			}

			before.insert(before.end(), ans.begin(), ans.end());

			if (hash != "") {
				m[hash] = before;
			}
			return before;
		}
	}
 
	return input;
}
 
int main() {
	string input; 
	cin >> input;
	vector<char> inputVec(input.begin(), input.end());
	vector<char> ans = solve(inputVec);

	//for (auto x : m) {
	//	cout << x.first <<  endl;
	//}
	//cout << seenCount << endl;
 
	for (auto x : ans) {
		cout << x;
	}
	cout << endl;
	//cout << ans.size() << endl;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: RUNTIME ERROR

Test 10

Group: 2

Verdict: RUNTIME ERROR

Test 11

Group: 2

Verdict: RUNTIME ERROR

Test 12

Group: 2

Verdict: RUNTIME ERROR

Test 13

Group: 2

Verdict: RUNTIME ERROR

Test 14

Group: 2

Verdict: RUNTIME ERROR