Submission #917227

#TimeUsernameProblemLanguageResultExecution timeMemory
917227devkudawlaZamjena (COCI18_zamjena)C++17
28 / 70
3 ms1744 KiB
// AUTHOR->DEV KUDAWLA //---------------------------------------------------- #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order(it return an iterator input is a value), order_of_key(input is index) typedef tree<long long, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define ll long long int #define vl vector<long long> #define nline cout << "\n" #define n_digit(n) (int)log10(n) + 1 #define msb(n) (int)(log2(n)) + 1 // it is 1 based #define pll pair<ll, ll> #define all(x) x.begin(), x.end() #define ternary(a, b, c) ((a) ? (b) : (c)) #define yesno(a) a ? cout << "Yes" : cout << "No" #define sroot(a) sqrt((long double)a) #define Max(a, b) max((ll)a, (ll)b) #define Min(a, b) min((ll)a, (ll)b) //---------------------------------------------------- template <class T1, class T2> ostream &operator<<(std::ostream &os, pair<T1, T2> &st) { cout << "{ " << st.first << " " << st.second << " }"; return os; } template <class T> istream &operator>>(istream &is, vector<T> &v) { int n = v.size(); for (int i = 0; i < n; i++) is >> v[i]; return is; } template <class T> istream &operator>>(istream &is, vector<vector<T>> &v) { int n = v.size(); int m = v[0].size(); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) is >> v[i][j]; return is; } template <class T> ostream &operator<<(std::ostream &os, vector<T> &v) { int n = v.size(); for (int i = 0; i < n; i++) os << v[i] << ((i == n - 1) ? "\n" : " "); return os; } template <class T> ostream &operator<<(std::ostream &os, vector<vector<T>> &v) { int n = v.size(); int m = v[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) os << v[i][j] << " "; os << "\n"; } return os; } template <class T> ostream &operator<<(std::ostream &os, set<T> &st) { cout << "---------------------------------\n"; for (auto i : st) cout << i << " "; nline; cout << "---------------------------------\n"; return os; } template <class T> ostream &operator<<(std::ostream &os, multiset<T> &st) { cout << "---------------------------------\n"; for (auto i : st) cout << i << " "; nline; cout << "---------------------------------\n"; return os; } template <class T1, class T2> ostream &operator<<(std::ostream &os, map<T1, T2> &st) { cout << "-------------------------------\n"; auto x = st.begin(); while (x != st.end()) { cout << x->first; cout << " -> "; cout << x->second; nline; x++; } cout << "-------------------------------\n"; return os; } template <class T> vector<T> add(vector<T> v1, vector<T> v2) { vector<T> v3 = v1; for (ll i = 0; i < v2.size(); i++) v3.push_back(v2[i]); return v3; } template <int D, typename T> struct Vector : public vector<Vector<D - 1, T>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename U, typename... Args> Vector(U n = U(), Args... args) : vector<Vector<D - 1, T>>(n, Vector<D - 1, T>(args...)) {} }; template <typename T> struct Vector<1, T> : public vector<T> { template <typename... Args> Vector(Args... args) : vector<T>(args...) {} }; inline ll power2(ll n) { ll answer = 0; if (n != 0) answer = msb(((ll)n) ^ ((ll)(n - 1))) - 1; return answer; } inline ll indexOf(ordered_multiset &st, ll value) { return st.order_of_key(value); } inline ll valueAt(ordered_multiset &st, ll index) { return *st.find_by_order(index); } inline ll indexOf(ordered_set &st, ll value) { return st.order_of_key(value); } inline ll valueAt(ordered_set &st, ll index) { return *st.find_by_order(index); } template <class T> void Distinct(T &v, bool sorting = true) { if (sorting) sort(begin(v), end(v)); v.resize(unique(begin(v), end(v)) - begin(v)); } //---------------------------------------------------- const ll N1 = 1000000007; const ll N2 = 998244353; //---------------------------------------------------- // MODULAR ARITHMETIC inline ll expo(ll a, ll b, ll mod = LONG_LONG_MAX) { ll res = 1; while (b > 0) { if (b & 1) res = ((__int128_t)res * a) % mod; a = ((__int128_t)a * a) % mod; b = b >> 1; } return res; } inline ll mminvprime(ll a, ll b) { return expo(a, b - 2, b); } // FOR PRIME inline ll mod_add(ll a, ll b, ll m = N1) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; } inline ll mod_mul(ll a, ll b, ll m = N1) { a = a % m; b = b % m; return (((__int128_t)(a * b) % m) + m) % m; } inline ll mod_sub(ll a, ll b, ll m = N1) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; } inline ll mod_div(ll a, ll b, ll m = N1) { a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m; } // only for prime m ll ncr(ll n, ll r, bool mod_version = false, ll mod = N1) { ll answer = 0; if (n >= r) { r = Min(r, n - r); if (mod_version == true) { ll a = 1; for (ll i = n; i >= n - r + 1; i--) a = mod_mul(a, i, mod); ll b = 1; for (ll i = 1; i <= r; i++) b = mod_mul(b, i, mod); b = mminvprime(b, mod); a = mod_mul(a, b, mod); answer = a; } else { ll a = 1; ll b = 1; for (ll i = n; i >= n - r + 1; i--) { a *= i; b *= (n - i + 1); ll g = __gcd(a, b); a /= g, b /= g; } answer = a / b; } } return answer; } ll factorial(ll n, bool mod_version = false, ll mod = N1) { ll answer = 1; if (mod_version == true) { for (int i = 2; i <= n; i++) answer = mod_mul(answer, i, mod); } else { for (int i = 2; i <= n; i++) answer *= i; } return answer; } bool is_prime(ll a) { if (a == 1) return false; for (ll i = 2; i * i <= a; i++) { if (a % i == 0) return false; } return true; } //---------------------------------------------------- map<ll, ll> prime_factors(ll n, bool debug = false) { map<ll, ll> answer; ll a = n; for (ll i = 2; i * i <= a; i++) while (a % i == 0) answer[i]++, a /= i; if (a > 1) answer[a]++; if (debug) { for (auto i : answer) cout << i.first << " -> " << i.second << "\n"; } return answer; } //---------------------------------------------------- // const int n_sieve = (20000008); // O(Nlog(log(N))) // vector<bool> prime_sieve(n_sieve + 1, true); void initialise_sieve(vector<bool> &prime_sieve) { prime_sieve[0] = false; prime_sieve[1] = false; for (ll i = 2; i * i < prime_sieve.size(); i++) if (prime_sieve[i] == true) for (ll j = 2; j * i < prime_sieve.size(); j++) prime_sieve[j * i] = false; } //---------------------------------------------------- // #define LOCAL_COMPILER #ifdef LOCAL_COMPILER #define dbg(x) \ cerr << "\n" \ << #x << " -> \n"; \ cout << x << "\n"; #endif #ifndef LOCAL_COMPILER #define dbg(x) #endif //---------------------------------------------------- // CODE STARTS HERE // TIME COMPLEXITY OF O(LOG(N)) AS IT IS NOT USING RANK // IT IS 1 BASED class DSU { public: vector<int> parent; // LIST OF PARENT OF EVERY NODE set<int> st; // LIST OF ALL ROOT NODES vector<int> sz; // SIZE OF COMPONENTS int n; DSU() {} DSU(int s) { n = s; parent.resize(n + 1); sz.resize(n + 1); for (int i = 1; i <= n; i++) sz[i] = 1, parent[i] = i, st.insert(i); } int FindRoot(int x) { if (parent[x] == x) return x; return parent[x] = FindRoot(parent[x]); } bool IsSame(int x, int y) { return FindRoot(x) == FindRoot(y); } void Merge(int x, int y) { int root1 = FindRoot(x), root2 = FindRoot(y); if (root1 == root2) return; if (root1 > root2) swap(root1, root2); parent[root2] = root1; st.erase(st.find(root2)); sz[root1] += sz[root2]; } int NoOfComponents() { return st.size(); } int SizeOfComponent(int x) { x = FindRoot(x); return sz[x]; } void Info() { cout << "Parent \n"; for (int i = 1; i <= n; i++) cout << parent[i] << " "; cout << "\n"; cout << "Size \n"; for (int i = 1; i <= n; i++) cout << SizeOfComponent(i) << " "; cout << "\n"; cout << "Root Nodes \n"; for (auto i : st) cout << i << " "; cout << "\n"; } }; //---------------------------------------------------- void solve(bool testCases = true) { ll T = 1; //->TEST CASES if (testCases) cin >> T; while (T--) { ll n; cin >> n; vector<string> a(n), b(n); cin >> a >> b; bool f = 1; DSU d(26); vl value(27, -1); for (ll i = 0; i < n and f; i++) { string A = a[i], B = b[i]; if (A.size() > B.size()) { reverse(all(B)); while (B.size() < A.size()) B.push_back('0'); reverse(all(B)); } else if (A.size() < B.size()) { reverse(all(A)); while (A.size() < B.size()) A.push_back('0'); reverse(all(A)); } ll len = A.size(); for (ll j = 0; j < len; j++) { bool g1 = (A[j] >= '0' and A[j] <= '9'); bool g2 = (B[j] >= '0' and B[j] <= '9'); if (g1 and g2) { ll c1 = A[j] - '0'; ll c2 = B[j] - '0'; if (c1 != c2) { f = 0; break; } } else if (g1 and !g2) { ll c1 = A[j] - '0'; ll c2 = B[j] - 'a' + 1; for (ll k = 1; k <= 26; k++) { if (d.IsSame(k, c2)) { if (value[k] == -1) { value[k] = c1; } else if (value[k] != c1) { f = 0; break; } } } } else if (!g1 and g2) { ll c1 = A[j] - 'a' + 1; ll c2 = B[j] - '0'; for (ll k = 1; k <= 26; k++) { if (d.IsSame(k, c1)) { if (value[k] == -1) { value[k] = c2; } else if (value[k] != c2) { f = 0; break; } } } } else { ll c1 = A[j] - 'a' + 1; ll c2 = B[j] - 'a' + 1; d.Merge(c1, c2); } } } for (ll i = 1; i <= 26; i++) { for (ll j = 1; j <= 26; j++) { if (d.IsSame(i, j) and (value[i] != value[j]) and !(value[i] == -1 or value[j] == -1)) { f = 0; break; } } } if (f) { cout << "DA"; } else cout << "NE"; nline; } //-------------------------------------------- // CODE ENDS HERE } //---------------------------------------------------- int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //------------------------------------------------ // initialise_sieve(prime_sieve); //------------------------------------------------ #ifdef LOCAL_COMPILER std::cout << std::fixed << std::setprecision(25); std::cerr << std::fixed << std::setprecision(10); auto start = std::chrono::high_resolution_clock::now(); #endif solve(false); #ifdef LOCAL_COMPILER auto stop = std::chrono::high_resolution_clock::now(); long double duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start).count(); std::cerr << "Time taken : " << duration / 1e9 << "s" << std::endl; #endif //------------------------------------------------ return 0; } //----------------------------------------------------

Compilation message (stderr)

zamjena.cpp: In function 'void initialise_sieve(std::vector<bool>&)':
zamjena.cpp:286:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  286 |             for (ll j = 2; j * i < prime_sieve.size(); j++)
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...