Submission #362048

#	Time	Username	Problem	Language	Result	Execution time	Memory
362048		idk321	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	396 ms	34156 KiB

scrivener

#include <iostream>

const int N = 1000005;

using namespace std;
typedef long long ll;

int cur;


struct Node
{
    Node* par1;
    Node* par2;
    int h;
    char c;

    Node(char c)
    {
        par1 = nullptr;
        par2 = nullptr;
        h = -1;
        this->c = c;
    }

    Node(Node* par, char c)
    {
        par1 = par;
        h = par->h + 1;
        int dist1 = par->par2->h - par->h;
        int dist2 = par->par2->par2->h - par->par2->h;
        if (dist1 == dist2)
        {
            par2 = par->par2->par2;
        } else
        {
            par2 = par;
        }
        this->c = c;
    }
};
Node* nodes[N];

char getKth(int i, Node* node)
{
    if (node->h == i) return node->c;
    if (node->par2->h >= i) return getKth(i, node->par2);
    return getKth(i, node->par1);
}



void Init()
{
    nodes[0] = new Node(' ');
    nodes[0]->par1 = nodes[0];
    nodes[0]->par2 = nodes[0];
    nodes[0]->h = -1;
    cur = 0;
}

void TypeLetter(char L) {

    cur++;
    nodes[cur] = new Node(nodes[cur - 1], L);
}

void UndoCommands(int U) {
    nodes[cur + 1] = nodes[cur - U];
    cur++;
}

char GetLetter(int P) {
    char c = getKth(P, nodes[cur]);
  return c;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40