제출 #1004578

#제출 시각아이디문제언어결과실행 시간메모리
1004578Ausp3x크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++17
12 / 100
1070 ms60960 KiB
// 人外有人,天外有天 // author: Ausp3x #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> typedef long long lng; typedef unsigned int uint; typedef unsigned long long ulng; using namespace std; using namespace __gnu_pbds; int const INF32 = 0x3f3f3f3f; lng const INF64 = 0x3f3f3f3f3f3f3f3f; unordered_map<lng, vector<lng>> Trie; vector<lng> history(1, -1); int getLen(lng c) { int len = 0; while (c != -1) { len += 1 << Trie[c].size() - 1; c = Trie[c][Trie[c].size() - 1]; } return len; } lng queryUp(lng c, int q) { int i = 0; while (q > 0) { if (i >= Trie[c].size()) return -INF64; if (q & 1) c = Trie[c][i]; i++; q >>= 1; } return c; } void debug() { cout << endl; cout << "Trie: " << endl; for (auto [k, v] : Trie) { cout << k << ": "; for (lng x : v) cout << x << ' '; cout << endl; } cout << endl; cout << "history: " << endl; for (lng x : history) cout << x << ' '; cout << endl; cout << endl; return; } void Init() { Trie[-1]; return; } void TypeLetter(char l) { lng prv = history.back(), p_lv = (prv != -1 ? abs(prv) % 100000000 / 26 : -1); lng cur = pow(-1, prv == -1) * (abs(prv) % 100000000 * 100000000 + (p_lv + 1) * 26 + (l - 'a')); if (Trie[cur].size() == 0) { Trie[cur].push_back(prv); for (int i = 1; i < 20; i++) { if (queryUp(prv, (1 << i) - 1) == -INF64) break; Trie[cur].push_back(queryUp(prv, (1 << i) - 1)); } } history.push_back(cur); return; } void UndoCommands(int u) { history.push_back(history[history.size() - u - 1]); return; } char GetLetter(int p) { int len = getLen(history.back()); return 'a' + (abs(queryUp(history.back(), len - p - 1)) % 100000000 % 26); } /* int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); Init(); TypeLetter('a'); TypeLetter('b'); cout << GetLetter(0) << endl; cout << GetLetter(1) << endl; UndoCommands(2); TypeLetter('a'); TypeLetter('b'); cout << GetLetter(0) << endl; cout << GetLetter(1) << endl; UndoCommands(2); UndoCommands(3); TypeLetter('a'); TypeLetter('b'); cout << GetLetter(0) << endl; cout << GetLetter(1) << endl; UndoCommands(2); TypeLetter('b'); TypeLetter('b'); cout << GetLetter(0) << endl; cout << GetLetter(1) << endl; debug(); // Init(); // TypeLetter('a'); // TypeLetter('b'); // cout << GetLetter(1) << endl; // TypeLetter('d'); // UndoCommands(2); // UndoCommands(1); // cout << GetLetter(2) << endl; // TypeLetter('e'); // UndoCommands(1); // UndoCommands(5); // TypeLetter('c'); // cout << GetLetter(2) << endl; // UndoCommands(2); // cout << GetLetter(2) << endl; return 0; } //*/

컴파일 시 표준 에러 (stderr) 메시지

scrivener.cpp: In function 'int getLen(lng)':
scrivener.cpp:22:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   22 |         len += 1 << Trie[c].size() - 1;
      |                     ~~~~~~~~~~~~~~~^~~
scrivener.cpp: In function 'lng queryUp(lng, int)':
scrivener.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (i >= Trie[c].size())
      |             ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...