Cod sursă (job #143318)

// Tabăra de pregătire a Lotului Național - Sovata 2014
// © 2014 Dragoș Vasile Oprică

#include <fstream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;

const int SQRT = 265;

struct list {
	char ch;
	list *next;
};

ifstream fin("sir3.in");
ofstream fout("sir3.out");

string initSir;
vector<string> dict;
int dictSize, querySize;

vector<int> sum;
vector<list *> pointer;

void insert(list *head, char ch, int poz, int copy, list *&copyList, int update, int ind) {
	list *tmp = new list;
		
	if (!poz) {
		tmp->ch = ch;
		tmp->next = head;
	}
	else {
		list *prev = head;
		head = head->next;
		while (--poz && head) {
			prev = head;
			head = head->next;
		}

		tmp->ch = ch;
		tmp->next = head;
		prev->next = tmp;
	}

	if(copy)
		copyList = tmp;
	if (update)
		sum[ind]++;
}

void createIndexes(list *head) {
	int cnt = 0;
	for (list *i = head; i; ++cnt, i = i->next)
		if (cnt % SQRT == 0) {
			pointer.push_back(i);
			sum.push_back(cnt);
			cnt = 0;
		}
	pointer.push_back(NULL);
	sum.push_back(cnt);
}

pair<int,int> find(int poz) {
	int mySum = sum[0];
	for (int i = 0; i + 1 < sum.size(); ++i) {
		if (mySum + sum[i + 1] >= poz)
			return make_pair(i, mySum);
		mySum += sum[i + 1];
	}

	return make_pair(sum.size() - 1, mySum);
}

inline int check(list *head, int ind, int poz) {
	while (poz-- && head)
		head = head->next;

	for (int i = 0; i < dict[ind].length(); ++i) {
		if (head == NULL || head->ch != dict[ind][i])
			return 0;
		
		head = head->next;
	}

	return 1;
}

int main () {
	list *headList = NULL;
	
	static string initSir; fin >> initSir;
	for(int i = initSir.length() - 1; i >= 0; --i)
		insert(headList, initSir[i], 0, 1, headList, 0, 0);

	fin >> dictSize;
	for(int i = 0; i < dictSize; ++i) {
		string word; fin >> word;
		dict.push_back(word);
	}

	createIndexes(headList);

	fin >> querySize;
    int last_ans = 0;
    int a, b;
	for(int i = 0; i < querySize; ++i) {
		int tip; fin >> tip;

		if(!tip) {
			int poz; char ch; fin >> poz >> ch >> a >> b;
             if(last_ans == 0)
                poz ^= a;
            else
                poz ^= b;   
			poz --;
			pair<int,int> indAndSum = find(poz);

			if (poz - indAndSum.second > 0)
				insert(pointer[indAndSum.first], ch, poz - indAndSum.second, 0, pointer[indAndSum.first], 1, indAndSum.first + 1);
			else
				insert(pointer[indAndSum.first], ch, poz - indAndSum.second, 1, pointer[indAndSum.first], 1, indAndSum.first + 1);
		}
		else {
			int poz, ind; fin >> poz >> ind >> a >> b;
			if(last_ans == 0)
                poz ^= a;
            else
                poz ^= b;   
            poz -= dict[ind - 1].length();
			pair<int,int> indAndSum = find(poz);

            
            last_ans = 0;
			if (poz - indAndSum.second >= 0) {
				last_ans = check(pointer[indAndSum.first], ind - 1, poz - indAndSum.second);
                fout << last_ans << "\n";
            }
			else 
				fout << "0\n";
		}
	}

	return 0;
}