Submission #361789

#	Time	Username	Problem	Language	Result	Execution time	Memory
361789		idk321	Crayfish scrivener (IOI12_scrivener)	C++11	34 / 100	649 ms	262148 KiB

scrivener

#include <iostream>

const int N = 1000000;

using namespace std;
typedef long long ll;

int cur;
int cl;
char word[N];


struct Node
{
    Node* l;
    Node* r;
    int sum;

    Node()
    {
        this->sum = 0;
        l = nullptr;
        r = nullptr;
    }
};
Node* root[N];



Node* cons(int a, int b)
{
    Node* node = new Node();
    if (a == b) return node;

    int mid = (a + b) / 2;
    node->l = cons(a, mid);
    node->r = cons(mid + 1, b);

    return node;
}

Node* add(int i, Node* org, int a, int b)
{
    Node* node = new Node();
    if (a == b)
    {
        node->sum = 1;
        return node;
    }

    int mid = (a + b) / 2;
    if (i <= mid)
    {
        node->l = add(i, org->l, a, mid);
        node->r = org->r;
    } else
    {
        node->l = org->l;
        node->r = add(i, org->r, mid + 1, b);
    }

    node->sum = (node->l)->sum + (node->r)->sum;
    //cout << a << " " << b << " " << node->sum << endl;
    return node;
}

int kth(Node* node, int i, int a, int b)
{
    if (a == b) return a;

    int mid = (a + b) / 2;
    if (node->l->sum >= i) return kth(node->l, i, a, mid);
    i -= node->l->sum;
    return kth(node->r, i, mid + 1, b);
}



void Init()
{
    root[0] = cons(0, N - 1);
    cur = 0;
    cl = -1;
}

void TypeLetter(char L) {

    cl++;
    cur++;
  word[cl] = L;
    root[cur] = add(cl, root[cur - 1], 0, N - 1);
}

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

char GetLetter(int P) {
    int i = kth(root[cur], P + 1, 0, N - 1);
  return word[kth(root[cur], P + 1, 0, N - 1)];
}

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:102:9: warning: unused variable 'i' [-Wunused-variable]
  102 |     int i = kth(root[cur], P + 1, 0, N - 1);
      |         ^

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