Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : Shopping is Fun!!
Source : Toph
Category : Dynamic Programing
Algorithm : SOS DP
Verdict : Accepted
- #include "bits/stdc++.h"
- #include "ext/pb_ds/assoc_container.hpp"
- #include "ext/pb_ds/tree_policy.hpp"
- #include "ext/rope"
-
- using namespace std;
- using namespace __gnu_pbds;
- using namespace __gnu_cxx;
-
-
-
-
-
-
-
- void trace(int x) { cerr << x; }
- void trace(long x) { cerr << x; }
- void trace(long long x) { cerr << x; }
- void trace(unsigned x) { cerr << x; }
- void trace(unsigned long x) { cerr << x; }
- void trace(unsigned long long x) { cerr << x; }
- void trace(float x) { cerr << x; }
- void trace(double x) { cerr << x; }
- void trace(long double x) { cerr << x; }
- void trace(char x) { cerr << '\'' << x << '\''; }
- void trace(const char *x) { cerr << '\"' << x << '\"'; }
- void trace(const string &x) { cerr << '\"' << x << '\"'; }
- void trace(bool x) { cerr << (x ? "true" : "false"); }
-
- template <typename A, typename B> void trace(const pair <A, B> &x) { cerr << '{'; trace(x.first); cerr << ','; trace(x.second); cerr << '}'; }
- template <typename A, typename B, typename C> void trace(const tuple <A, B, C> &x) { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << '}'; }
- template <typename A, typename B, typename C, typename D> void trace(const tuple <A, B, C, D> &x) { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << ','; trace(get <3> (x)); cerr << '}'; }
- template <typename T> void trace(const T &x) { int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), trace(i); cerr << "}"; }
- template <size_t N> void trace(bitset <N> v) { cerr << '{'; for (size_t i = 0; i < N; i++) cerr << static_cast <char> ('0' + v[i]); cerr << '}'; }
- void _print() { cerr << "]\n"; }
- template <typename T, typename... V> void _print(T t, V... v) { trace(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
-
- #ifndef ONLINE_JUDGE
- #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
- #else
- #define debug(x...)
- #endif
-
- template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
- template <typename T1, typename T2> using ordered_map = tree <T1, T2, less <T1>, rb_tree_tag, tree_order_statistics_node_update>;
-
- template <class T> bool MIN(T &a, T b) { return a > b ? (a = b, true) : false; }
- template <class T> bool MAX(T &a, T b) { return a < b ? (a = b, true) : false; }
-
- template <class T> T binaryExpo(T a, T p) { if (p == 0) { return 1LL; } if (p == 1) { return a; } if (p & 1) { return a * binaryExpo(a, p - 1); } T ret = binaryExpo(a, p / 2); return ret * ret; }
- template <class T> T bigMod(T a, T p, T m) { if (p == 0) { return 1LL % m; } if (p == 1) { return a % m; } if (p & 1) { return (a % m * bigMod(a, p - 1, m)) % m; } T ret = bigMod(a, p / 2, m) % m; return (ret * ret) % m; }
- template <class T> T modInv(T a, T m) { return bigMod(a, m - 2, m); }
-
- template <typename T> string num_str(T num) { stringstream ss; ss << num; return ss.str(); }
- long long str_num(string s) { long long num; istringstream iss(s); iss >> num; return num; }
-
- inline long long ON(long long mask, int pos) { return mask |= (1LL << pos); }
- inline long long OFF(long long mask, int pos) { return mask &= ~(1LL << pos); }
- inline long long TOGGLE(long long mask, int pos) { return mask ^= (1LL << pos); }
- inline bool CHECK(long long mask, int pos) { return (bool)(mask >> pos & 1LL); }
-
- inline int ONE(long long mask) { return __builtin_popcountll(mask); }
- inline int LZERO(long long mask) { return 31 - __builtin_clzll(mask); };
- inline int TZERO(long long mask) { return __builtin_ctzll(mask); };
-
-
-
- int dr[] = {+0, +0, +1, -1, +1, +1, -1, -1};
- int dc[] = {+1, -1, +0, +0, +1, -1, +1, -1};
-
-
-
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
-
- #define ll long long int
- #define ull unsigned long long int
- #define endl '\n'
- #define pii pair <int, int>
- #define pll pair <ll, ll>
- #define mk make_pair
- #define ff first
- #define ss second
- #define all(a) (a).begin(), (a).end()
- #define rall(a) (a).rbegin(), (a).rend()
- #define eb emplace_back
- #define pb push_back
- #define pf push_front
- #define allUpper(a) transform(all(a), a.begin(), :: toupper)
- #define allLower(a) transform(all(a), a.begin(), :: tolower)
- #define LINE cerr << __LINE__ << " ";
- #define memo(a, b) memset(a, b, sizeof a)
- #define ook order_of_key
- #define fbo find_by_order
-
- #define int long long int
-
- static const int maxn = (1 << 20) + 5;
- static const int logn = 19;
- static const long long MOD = 1e9 + 7;
- static const long long INF = 1e18;
-
- int counter[maxn];
- vector <int> masks;
-
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cout.precision(12);
-
- #ifndef ONLINE_JUDGE
- freopen("in.txt", "r", stdin);
- #endif // ONLINE_JUDGE
-
- int tc;
- cin >> tc;
- while (tc--) {
- int n, m;
- cin >> n >> m;
- vector <int> masks(n);
- vector <int> sos(1 << m);
- int zero = 0;
- int nonzero = 0;
- for (int i = 0; i < n; i++) {
- int mask = 0;
- for (int j = m - 1; j >= 0; j--) {
- int x;
- cin >> x;
- mask += (1 << j) * x;
- }
- masks[i] = mask;
- if (mask) {
- sos[mask]++;
- }
- else {
- zero++;
- }
- }
- debug(masks);
- for (int i = 0; i < m; i++) {
- for (int mask = 0; mask < (1 << m); mask++) {
- if (mask >> i & 1) {
- sos[mask] += sos[mask ^ (1 << i)];
- }
- }
- }
- int ans = 0;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- if (masks[i] and masks[j] and ((masks[i] & masks[j]) == 0)) {
- int mymask = ((1 << m) - 1) ^ (masks[i] | masks[j]);
- debug(masks[i], masks[j], mymask, sos[mymask]);
- ans += sos[mymask];
- nonzero++;
- }
- }
- }
- debug(zero, nonzero);
- ans /= 3;
- ans += zero * nonzero;
- ans += zero * (zero - 1) * (n - zero) / 2;
- ans += zero * (zero - 1) * (zero - 2) / 6;
- cout << ans << endl;
- }
-
- #ifndef ONLINE_JUDGE
- cerr << endl << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
- #endif // ONLINE_JUDGE
-
- return 0;
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.