Submission #42150

#TimeUsernameProblemLanguageResultExecution timeMemory
42150wasylCezar (COCI16_cezar)C++11
10 / 100
2 ms608 KiB
#include <bits/stdc++.h> #ifndef dbg #define dbg(...) #endif #define st first #define nd second #define all(x) begin(x), end(x) #define rsz(...) resize(__VA_ARGS__) #define psh(...) push_back(__VA_ARGS__) #define emp(...) emplace_back(__VA_ARGS__) #define prt(...) print(cout, __VA_ARGS__) #define dprt(...) dbg(print(cerr,__VA_ARGS__)) #define dmp(...) dprt(#__VA_ARGS__, '=', __VA_ARGS__) using namespace std;using ll=long long; template<typename t>using V=vector<t>; template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';} template<typename t, typename... A>void print (ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);} int n, siz; V< int > top; V< V< int > > gr; V< pair< int, string > > tab; void gen (int lo, int hi, int v = 0) { if (lo >= hi or v == siz) return; dprt(lo, hi); string s; while (lo <= hi) { char c = tab[lo].nd[v]; int poplo = lo; while (lo + 1 <= hi and tab[lo + 1].nd[v] == c) ++lo; s += string(1, c); gen(poplo, lo, v + 1); ++lo; } for (int i = 1; i < s.size(); ++i) gr[s[i - 1] + 1 - 'a'].psh(s[i] + 1 - 'a'); dprt(s); } inline bool topo () { int id = 0; V< int > deg(27); top.rsz(27); for (int i = 0; i < 27; ++i) for (int k : gr[i]) ++deg[k]; queue< int > Q; for (int i = 0; i < 27; ++i) if (deg[i] == 0) Q.push(i); while (!Q.empty()) { int v = Q.front(); Q.pop(); top[v] = id++; top.psh(v); for (int s : gr[v]) if (--deg[s] == 0) Q.push(s); } return id == 27 and top[0] == 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; tab.rsz(n); gr.rsz(27); for (int i = 0; i < n; ++i) cin >> tab[i].nd; for (int i = 0; i < n; ++i) cin >> tab[i].st; sort(all(tab)); for (auto& p : tab) siz = max(siz, (int)p.nd.size()); for (auto& p : tab) p.nd.rsz(siz, 'a' - 1); dbg( for (auto& p : tab) dprt(p.nd); ); gen(0, n - 1); dbg( for (int i = 0; i < 27; ++i) { cerr << i << ": "; for (int s : gr[i]) cerr << s << ' '; cerr << '\n'; } ); if (topo()) { prt("DA"); for (int i = 1; i < 27; ++i) if (i != 0) cout << (char)(top[i] + 'a' - 1); cout << '\n'; } else prt("NE"); }

Compilation message (stderr)

cezar.cpp: In function 'void gen(int, int, int)':
cezar.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < s.size(); ++i)
                       ^
#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...
#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...