HIIT Generation

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


ll n;
vector<char> cc;
vector<char> vals (1000000);
vector<int> llnext (1000000);
vector<int> llprev (1000000);
vector<int> hpos;
vector<int> tpos;
ll p;


void replh(int ind) {
  //  cout << "Replh: " << ind << endl;
  vals[p] = 'I';
  llnext[p] = p+1;
  llprev[p] = ind;
  vals[p+1] = 'I';
  llnext[p+1] = p+2;
  llprev[p+1] = p;
  vals[p+2] = 'T';
  llnext[p+2] = llnext[ind];
  llprev[p+2] = p+1;
  tpos.push_back(p+2);

  llprev[llnext[ind]] = p+2;

  llnext[ind] = p;

  
  p += 3;
}

int main() {

  cin.tie(NULL);
  std::ios::sync_with_stdio(false);

  cin >> n;

  cc.resize(n);
  for (int i=0; i<n; i++) {
    cin >> cc[i];
  }

  vals[0] = 'H';
  vals[1] = 'I';
  vals[2] = 'I';
  vals[3] = 'T';
  for (int i=0; i<4; i++) {
    llnext[i] =(i+1);
    llprev[i] =(i-1);
  }
  llnext[3] = -1;

  hpos.push_back(0);
  tpos.push_back(3);

  p = 4;
  
  for (int i=0; i<n; i++) {
    if (cc[i] == 'H') {
      for (auto ind : hpos) {
	//	cout << "To replh: " << i << " " << ind << endl;
	//	cout << "Hpos: " << hpos.size() << endl;
	replh(ind);
      }
    }
    if (cc[i] == 'T') {
      for (auto ind : tpos) {
	vals[p] = 'H';
	llnext[p] = p+1;
	llprev[p] = llprev[ind];
	vals[p+1] = 'I';
	llnext[p+1] = p+2;
	llprev[p+1] = p;
	vals[p+2] = 'I';
	llnext[p+2] = ind;
	llprev[p+2] = p+1;
	hpos.push_back(p);
	llnext[llprev[ind]] = p;
	llprev[ind] = p+2;
	
  
	p += 3;
      }
    }
    if (cc[i] == 'I') {
      int oldp = p;
      for (int ind=0; ind<oldp; ind++) {
	if (vals[ind] != 'I') { continue; }

	vals[ind] = 'H';
	hpos.push_back(ind);

	replh(ind);
      }
    }
  }

  for (int i=0; i!=-1; i = llnext[i]) {
    cout << vals[i];
  }
  cout << endl;
  
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED