Monistus

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

void solve(int start, int end) {
	maxSize = max((int)input.size(), maxSize);
	//cout << maxSize << endl;

//	string hash = "";
        //
	//for (int i=start; i<n; i++) {
	//	seenCount++;
	//	hash += input[i];
	//}

	//if (m.count(hash)) { //size limit?
	//}

	//cout << "hasb: " <<  hash << endl;
	
	int n = end;
	for (int i=start; i<n; i++) {
		if (i >= (int)input.size()) break;
		char ch = input[i];
		int digit = ch - '0'; 
 
		if (digit > 0 && digit <= 9) {
			//before.insert(before.end(), input.begin(), input.begin()+i);

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

			//cout << "input: ";
			//for (auto x : input) cout << x;
			//cout << endl;

			//cout << "expanded: ";
			//for (auto x : expanded) cout << x;
			//cout << endl;

			bool overlaps = false;
			int s = (int) expanded.size();

			string hash;
			int length = s;

			hash += ch;
			for (int j=0; j<s; j++) {
				char ch2 = expanded[j];
				hash += ch2;

				int d = ch2 - '0'; 
				if (d > 0 && d <= 9) {
					length += d-1; 
					if (j + d >= s) {
						overlaps = true;
						break;
					}
				}
			}
			//cout << hash << ": " << length << endl;

			if (overlaps) {
				input.insert(input.begin()+i, expanded.begin(), expanded.end());

				//cout << "solving overlap for " << hash << " from " << i << " to " << input.size() << ": " <<endl;
				n = input.size();
				//solve(i, input.size());
			} else {
				if (m.count(hash)) {
					seenCount++;
					vector<char> hashed = m[hash];					
					input.insert(input.begin()+i, hashed.begin(), hashed.end());

					//cout << "seen: " << hash << endl;
					//cout << "seen for hash " << hash << " from " << i+length << " to " << input.size() << ": " << endl;
					//i+=length;
					n = input.size();
					//solve(i+length, input.size());
				} else {
					//cout << hash << endl;
					input.insert(input.begin()+i, expanded.begin(), expanded.end());

					solve(i, i+s); 
					//cout << hash << " " << length << " " << overlaps << endl;
					vector<char> solved(input.begin()+i, input.begin()+i+length);

					//cout << "solved for hash " << hash << " from " << i << " to " << i+s << ": ";
					//for (auto x : solved) cout << x;
					//cout << endl;

					m[hash] = solved;

					//i += length;
					//n+=length;
					//n = input.size();
					//solve(i+length, input.size()); 
				}
			}


			//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;
			//
		}
	}
}
 
int main() {
	string prompt;
	cin >> prompt;

	input.insert(input.end(), prompt.begin(), prompt.end());

	solve(0, 501010);
	//solve(0, input.size());

	//cout << "-==================|" <<endl;
	//for (auto x : m) {
	//	cout << x.first << ": ";
	//	for (auto y : x.second) {
	//		cout << y;
	//	}
	//	cout << endl;
	//}
	//cout << seenCount << endl;
 
	for (auto x : input) {
		cout << x;
	}
	cout << endl;

	//cout << maxSize << 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: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED