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