Submission #1184989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184989		Gabp	Crayfish scrivener (IOI12_scrivener)	C++20	12 / 100	137 ms	39816 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;

int cnt = 0;
const int N = 1e6 + 5;
int sz[N];
int idx[N];
vector<pair<int,char>> memo[N];

void Init() {
    sz[0] = 0;
    idx[0] = 0;
}

void TypeLetter(char L) {
    int x = sz[cnt++];
    idx[cnt] = cnt;
    sz[cnt] = x + 1;
    memo[x].push_back({cnt, L});
}

void UndoCommands(int U) {
    int prev = idx[cnt++ - U];
    idx[cnt] = prev;
    sz[cnt] = sz[prev];
}

char GetLetter(int P) {
    auto it = lower_bound(memo[P].begin(), memo[P].end(), make_pair(cnt + 1, '\0'));
    it--;
    return it->second;
}

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