Submission #720661

#	Time	Username	Problem	Language	Result	Execution time	Memory
720661		thimote75	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1070 ms	87304 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>
#define cdata vector<char>
#define igrid vector<idata>

idata letterCount;
idata depth;
cdata letter;
idata parents;
igrid parents_2k;

int addElement (int parent) {
  int lC_p = parent < 0 ? 0 : letterCount[parent];
  int de_p = parent < 0 ? -1 : depth[parent];

  letterCount.push_back(lC_p);
  letter     .push_back(0);
  parents    .push_back(parent);
  depth      .push_back(de_p + 1);

  vector<int> p2K;
  p2K.push_back(parent);

  int lP = parent;
  int i  = 0;
  while (lP != -1 && i < parents_2k[lP].size()) {
    lP = parents_2k[lP][i];
    i ++;
    p2K.push_back(lP);
  }
  parents_2k.push_back(p2K);

  return parents_2k.size() - 1;
}
int lastElement () {
  return parents_2k.size() - 1;
}
int jump (int l, int k) {
  for (int h = 0; h < 21; h ++)
    if (((1 << h) & k) != 0)
      l = parents_2k[l][h];
  
  return l;
}
int find (int element, int textId) {
  int a = 0;
  int b = depth[element];

  while (b - a > 1) {
    int c = (a + b) >> 1;
    int e = jump(element, c);

    if (letterCount[e] >= textId) a = c;
    else b = c;
  }

  return jump(element, a);
}

void Init() {
  int el = addElement(-1);
}

void TypeLetter(char L) {
  int el = addElement( lastElement() );
  letterCount[el] ++;
  letter     [el] = L;
}

void UndoCommands(int U) {
  int el = addElement( lastElement() - U );
}

char GetLetter(int P) {
  int pos = find(lastElement(), P + 1);

  return letter[pos];
}

Compilation message (stderr)

scrivener.cpp: In function 'int addElement(int)':
scrivener.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while (lP != -1 && i < parents_2k[lP].size()) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~
scrivener.cpp: In function 'void Init()':
scrivener.cpp:65:7: warning: unused variable 'el' [-Wunused-variable]
   65 |   int el = addElement(-1);
      |       ^~
scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:75:7: warning: unused variable 'el' [-Wunused-variable]
   75 |   int el = addElement( lastElement() - U );
      |       ^~

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