QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #222449 | #6556. Text Editor | ucup-team004# | 0 | 2ms | 5780kb | C++20 | 5.4kb | 2023-10-21 17:15:44 | 2023-10-21 17:15:44 |
answer
#include <bits/stdc++.h>
using i64 = long long;
struct Node {
int l = 0;
int r = 0;
i64 len = 0;
char ch = '\0';
};
constexpr int N = 1E7;
Node t[N];
int tot = 0;
void pull(int a) {
t[a].len = t[t[a].l].len + 1 + t[t[a].r].len;
}
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int copy(int a) {
int b = ++tot;
t[b] = t[a];
return b;
}
int build(const std::string &s, int l, int r) {
if (r - l == 0) {
return 0;
}
int x = (l + r) / 2;
int a = ++tot;
t[a].l = build(s, l, x);
t[a].r = build(s, x + 1, r);
t[a].ch = s[x];
pull(a);
return a;
}
int merge(int a, int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
if (rng() % (t[a].len + t[b].len) < t[a].len) {
int c = copy(a);
t[c].r = merge(t[a].r, b);
pull(c);
return c;
} else {
int c = copy(b);
t[c].l = merge(a, t[b].l);
pull(c);
return c;
}
}
std::pair<int, int> split(int a, i64 k) {
if (k == 0) {
return {0, a};
}
if (k == t[a].len) {
return {a, 0};
}
if (k <= t[t[a].l].len) {
auto [l, r] = split(t[a].l, k);
int c = copy(a);
t[c].l = r;
pull(c);
return {l, c};
} else {
auto [l, r] = split(t[a].r, k - 1 - t[t[a].l].len);
int c = copy(a);
t[c].r = l;
pull(c);
return {c, r};
}
}
void print(int a, i64 l, i64 r) {
if (l < t[t[a].l].len) {
print(t[a].l, l, std::min(r, t[t[a].l].len));
}
if (l <= t[t[a].l].len && r > t[t[a].l].len) {
std::cout << t[a].ch;
}
if (r > t[t[a].l].len + 1) {
print(t[a].r, std::max(0LL, l - 1 - t[t[a].l].len), r - 1 - t[t[a].l].len);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::string line;
std::getline(std::cin, line);
std::vector<int> text{0};
int clip = 0;
std::vector<int> history{0};
int current = 0;
std::string input;
std::function<void(std::string, bool)> work = [&](std::string line, bool second) {
std::stringstream cmd(line);
input += line + '\n';
std::string op;
cmd >> op;
int a = text[history[current]];
if (op == "insert") {
i64 p;
std::string str;
cmd >> p >> str;
auto [L, R] = split(a, p);
history.resize(current + 1);
history.push_back(text.size());
text.push_back(merge(merge(L, build(str, 0, str.size())), R));
current += 1;
} else if (op == "erase") {
i64 l, r;
cmd >> l >> r;
auto [LM, R] = split(a, r);
auto [L, M] = split(LM, l);
history.resize(current + 1);
history.push_back(text.size());
text.push_back(merge(L, R));
current += 1;
} else if (op == "print") {
if (second) {
return;
}
i64 l, r;
cmd >> l >> r;
print(a, l, r);
std::cout << "\n";
} else if (op == "copy") {
i64 l, r;
cmd >> l >> r;
auto [LM, R] = split(a, r);
auto [L, M] = split(LM, l);
clip = M;
} else if (op == "cut") {
i64 l, r;
cmd >> l >> r;
auto [LM, R] = split(a, r);
auto [L, M] = split(LM, l);
clip = M;
history.resize(current + 1);
history.push_back(text.size());
text.push_back(merge(L, R));
current += 1;
} else if (op == "paste") {
i64 p;
cmd >> p;
auto [L, R] = split(a, p);
history.resize(current + 1);
history.push_back(text.size());
text.push_back(merge(merge(L, clip), R));
current += 1;
} else if (op == "serialize") {
if (second) {
return;
}
for (auto c : input) {
int x = c / 16;
int y = c % 16;
std::cout << char(x < 10 ? '0' + x : 'A' + x - 10) << char(y < 10 ? '0' + y : 'A' + y - 10);
}
std::cout << "\n";
} else if (op == "deserialize") {
std::string str;
cmd >> str;
std::string t;
for (int i = 0; i < str.size(); i += 2) {
char x = str[i], y = str[i + 1];
int u = std::isdigit(x) ? x - '0' : x - 'A' + 10;
int v = std::isdigit(y) ? y - '0' : y - 'A' + 10;
t += u * 16 + v;
}
std::stringstream input(t);
while (std::getline(input, line)) {
work(line, true);
}
} else if (op == "undo") {
if (current > 0) {
current -= 1;
}
} else if (op == "redo") {
if (current + 1 < history.size()) {
current += 1;
}
} else {
assert(false);
}
};
for (int i = 1; i <= n; i++) {
std::getline(std::cin, line);
work(line, false);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3512kb
First Run Input
17 insert 0 abcdef print 0 6 erase 4 5 print 0 5 copy 0 3 paste 1 print 0 8 cut 2 4 print 0 6 undo print 0 8 paste 6 print 0 10 redo redo print 0 10 serialize
First Run Output
abcdef abcdf aabcbcdf aabcdf aabcbcdf aabcbcbcdf aabcbcbcdf 696E736572742030206162636465660A7072696E74203020360A6572617365203420350A7072696E74203020350A636F7079203020330A706173746520310A7072696E74203020380A637574203220340A7072696E74203020360A756E646F0A7072696E74203020380A706173746520360A7072696E7420...
Second Run Input
2 deserialize 696E736572742030206162636465660A7072696E74203020360A6572617365203420350A7072696E74203020350A636F7079203020330A706173746520310A7072696E74203020380A637574203220340A7072696E74203020360A756E646F0A7072696E74203020380A706173746520360A7072696E7420302031300A7265646F0A7265646F0A7072696E74203020...
Second Run Output
aabcbcbcdf
result:
ok stage 2 is ok!
Test #2:
score: 100
Accepted
time: 1ms
memory: 3436kb
First Run Input
1 serialize
First Run Output
73657269616C697A650A
Second Run Input
1 deserialize 73657269616C697A650A
Second Run Output
result:
ok stage 2 is ok!
Test #3:
score: 100
Accepted
time: 1ms
memory: 3560kb
First Run Input
31 undo redo redo undo undo undo redo undo redo undo undo undo undo undo redo redo undo undo redo undo redo redo redo undo undo undo redo undo redo redo serialize
First Run Output
756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A7265646F0A756E646F0A756E646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A...
Second Run Input
31 deserialize 756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A7265646F0A756E646F0A756E646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A72656...
Second Run Output
result:
ok stage 2 is ok!
Test #4:
score: 100
Accepted
time: 1ms
memory: 3552kb
First Run Input
31 undo redo redo undo undo redo redo redo undo undo undo redo redo undo redo undo redo undo redo redo redo undo redo undo redo redo undo undo redo undo serialize
First Run Output
756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A756E646F0A...
Second Run Input
31 deserialize 756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A7265646F0A756E646F0A7265646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A72656...
Second Run Output
result:
ok stage 2 is ok!
Test #5:
score: 100
Accepted
time: 0ms
memory: 3564kb
First Run Input
31 undo undo undo redo redo redo redo undo undo redo redo undo undo undo redo redo redo redo undo redo redo undo undo undo redo undo undo undo undo redo serialize
First Run Output
756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A7265646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A756E646F0A756E646F0A756E646F0A7265646F0A...
Second Run Input
31 deserialize 756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A7265646F0A756E646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A7265646F0A7265646F0A7265646F0A756E646F0A7265646F0A7265646F0A756E646F0A756E646F0A756E646F0A7265646F0A756E646F0A756E646F0A756E646F0A756E6...
Second Run Output
result:
ok stage 2 is ok!
Test #6:
score: 100
Accepted
time: 2ms
memory: 5780kb
First Run Input
1001
insert 0 u]^rGH]V+A3/VCu}4-dod,hyG&]WkL1)rg$W4\W0XL7sfyA[GNpfX2rx8Sc6$fmzW&x3E//Q0M\7=?Io7mupWV9Y4z6aY4E9ia$S{1KfioW29lST';?emw,Upk.b`^tl.O^btxvAx>:=&rC@6k`[GQCv;s[myKiSV1tp!Z)bj:
copy 0 170
paste 170
copy 0 340
paste 340
cut 415 652
copy 0 443
paste 443
cut 282 500
erase 0 576
copy 0 92
paste ...
First Run Output
/VCu}4-dod,hyG&]WkL1)rg)bj:/VCu}4-dyKlPm}+uRG&]WkL1)rg)bj:/V)bj:/VCu})bj:/)rg)bj:/VCG&]WkL1)rg)bj:/VCu}4-dyKlPm}+uRG&]WkL1)rg)bj:/V) /VCu}4/VCu}4 4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/VCu}4/VCu} Cu4//VCuCu}4//VCu}4/Cu}4//VCu}4/VCu}CuCu}4/u}4//VCu}4/VCu}CuC...
Second Run Input
1001 deserialize 696E73657274203020755D5E7247485D562B41332F5643757D342D646F642C687947265D576B4C312972672457345C5730584C37736679415B474E7066583272783853633624666D7A57267833452F2F51304D5C373D3F496F376D757057563959347A366159344539696124537B314B66696F5732396C5354273B3F656D772C55706B2E62605E746C2E4F5E627...
Second Run Output
4/}4/u}4/ uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...
result:
ok stage 2 is ok!
Test #7:
score: 100
Accepted
time: 2ms
memory: 3780kb
First Run Input
1001
insert 0 w,[bkd4hhpQ'MmMc:IK6O#ZVGwy`{iW,dmR]!Zo)u{|F*Y_"SI9dsR.a@Y@5YU[vEAya3.Y<C~U+JY66Co-HfJ*WN
undo
redo
erase 75 84
cut 3 78
paste 2
undo
erase 1 3
redo
erase 1 3
copy 0 1
cut 0 1
redo
redo
redo
undo
copy 0 1
paste 1
redo
undo
copy 0 1
undo
undo
copy 0 4
cut 1 5
undo
cut 0 5
redo
redo
undo...
First Run Output
w,[,[WNWN
bb{b{
NNNN
*
*
*
AERER
ERRKRR
696E73657274203020772C5B626B643468687051274D6D4D633A494B364F235A56477779607B69572C646D525D215A6F29757B7C462A595F225349396473522E614059403559555B7645417961332E593C437E552B4A593636436F2D48664A2A574E0A756E646F0A7265646F0A65726173652037352038340A63757420332037380A...
Second Run Input
1001 deserialize 696E73657274203020772C5B626B643468687051274D6D4D633A494B364F235A56477779607B69572C646D525D215A6F29757B7C462A595F225349396473522E614059403559555B7645417961332E593C437E552B4A593636436F2D48664A2A574E0A756E646F0A7265646F0A65726173652037352038340A63757420332037380A706173746520320A756E646...
Second Run Output
\HKrk`Qy`e6Jpyc/>5Kw}A,syx1^4Ej[] p pppp pp p R[Gam_HY~-PG
result:
ok stage 2 is ok!
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 4268kb
First Run Input
1001
insert 0 R9cgb7*%)7^_EA4jD9J^u<P0QmI/lYpy4J/L"?KY?_<-""SZH]`e)D=8'XLd5XF3l/BPwfQ6Pqd6x{[U``+lywj-r0AiLtCyIOw_(}rPBcgVg2,T\2YB0v#J)'Q2A$ZF@-t$.vKp~Z\c9rQY?js|<\Fl"um?oLARgQ`]q+Ci)Yh]|9bm-!t2/$@gC)p&e&{+T$mtW4TnoG_J\yBE@#1X9;S6swU#qBX"./2uUjc*rP6]{
copy 0 237
paste 0
copy 0 474
paste 0
undo
copy ...
First Run Output
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{...
Second Run Input
1001 deserialize 696E736572742030205239636762372A2529375E5F4541346A44394A5E753C5030516D492F6C597079344A2F4C223F4B593F5F3C2D2222535A485D606529443D3827584C64355846336C2F42507766513650716436787B5B5560602B6C79776A2D723041694C744379494F775F287D72504263675667322C545C3259423076234A2927513241245A46402D74242...
Second Run Output
{{
result:
wrong answer wrong answer on query 8 (in the first run)