Submission #915577

#TimeUsernameProblemLanguageResultExecution timeMemory
915577josanneo22Type Printer (IOI08_printer)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #include <random> using namespace std; namespace NEO { std::mt19937 cincai(std::chrono::steady_clock::now().time_since_epoch().count()); using i64 = long long; #define pb push_back #define mp make_pair #define cs constexpr #define L(i,j,k) for(int i=(j);i<=(k);++i) #define R(i,j,k) for(int i=(j);i>=(k);--i) #define all(x) x.begin(),x.end() #define me(x,a) memset(x,a,sizeof(x)) #ifndef ONLINE_JUDGE #include "debug.h" #else #define dbg(...) 43 #endif } using namespace NEO; struct node { int nxt[26]; bool is_longest, finish_word; node() { me(nxt, 0); is_longest = false; finish_word = false; } }; cs int _N = 25000 * 21; int tot = 0; node trie[_N]; void build(string S) { int M = S.size(), P = 0; for (int i = 0; i < M; i++) { int nw = S[i] - 'a'; if (trie[P].nxt[nw] == 0) { trie[P].nxt[nw] = ++tot; trie[tot] = node(); } P = trie[P].nxt[nw]; } trie[P].finish_word = true; } void paint(string S) { int P = 0; for (int i = 0; i < (int)S.size(); i++) { int nw = S[i] - 'a'; P = trie[P].nxt[nw]; trie[P].is_longest = true; } } string ans = ""; void dfs(int P) { int longest = -1; if (trie[P].finish_word) ans += 'P'; for (int i = 0; i < 26; i++) { int next_node = trie[P].nxt[i]; if (trie[next_node].is_longest) longest = i; else if (next_node != 0) { ans += (i + 'a'); dfs(next_node); } } if (longest != -1) { ans += (longest + 'a'); dfs(trie[P].nxt[longest]); } else if (longest == -1 && trie[P].is_longest) return; else ans += '-'; } namespace fast { #pragma GCC optimize(Ofast) #pragma GCC optimization (unroll-loops) #pragma GCC target(avx,avx2,fma) #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native) #pragma GCC optimize(3) #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") } using namespace fast; inline string read_string() { char ch = getchar(); string st1 = ""; while (!((ch >= 'A') && (ch <= 'Z'))) ch = getchar(); while ((ch >= 'A') && (ch <= 'Z')) st1 += ch, ch = getchar(); return st1; } char buf[1 << 23], * p1 = buf, * p2 = buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; } template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); } template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) ps(x / 10); putchar(x % 10 + '0'); } template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); } #define sp putchar(' ') #define nl putchar('\n') int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; re(N); vector<string> s(N + 1); L(i, 1, N) s[i] = read_string(); string longest = ""; L(i, 1, N) { build(s[i]); if (longest.size() < s[i].size()) longest = s[i]; } paint(longest); dfs(0); ps(ans.size()); nl; for (auto& c : ans) putchar(c), nl; }

Compilation message (stderr)

printer.cpp:19:14: fatal error: debug.h: No such file or directory
   19 |     #include "debug.h"
      |              ^~~~~~~~~
compilation terminated.