Submission #550542

#	Time	Username	Problem	Language	Result	Execution time	Memory
550542		marvinthang	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	103 ms	125020 KiB

skyscraper

/*************************************
*    author: marvinthang             *
*    created: 18.04.2022 17:13:13    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1};
const int MAX = 1e2 + 2;
const int MOD = 1e9 + 7;

namespace Mod {

    inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
    #ifdef __GNUC__
        asm(
            "divl %4 \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (y)
        );
    #else
        __asm {
            mov edx, dword ptr[xh];
            mov eax, dword ptr[xl];
            div dword ptr[y];
            mov dword ptr[d], eax;
            mov dword ptr[m], edx;
        };
    #endif
        out_d = d; out_m = m;
    }

    template <int MOD>
    struct ModInt {
        
        unsigned int val;

        ModInt(void): val(0) {}
        ModInt(const long long &x) { *this = x; }

        ModInt & normalize(const unsigned int &v) {
            val = v >= MOD ? v - MOD : v;
            return *this;
        }

        bool operator ! (void) { return !val; }

        ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
        ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }

        ModInt operator - (void) { return normalize(MOD - val); }

        ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
        ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
        ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }

        ModInt & operator *= (const ModInt &other) {
            unsigned dummy;
            fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
            return *this;
        }

        ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
        ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
        ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
        ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }

        ModInt pow(const ModInt &Exp) const {
            int n = Exp.val;
            assert(n >= 0);
            ModInt res = 1, a = *this;
            while (n) {
                if (n & 1) res = res * a;
                a = a * a;
                n >>= 1;
            }
            return res;
        }

        ModInt pow(long long Exp) const {
            assert(Exp >= 0);
            ModInt res = 1, a = *this;
            while (Exp) {
                if (Exp & 1) res = res * a;
                a = a * a;
                Exp >>= 1;
            }
            return res;
        }

        ModInt inv(void) const { return pow(MOD - 2); }

        ModInt & operator ++ (void) { return *this += 1; }
        ModInt & operator -- (void) { return *this -= 1; }
        ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
        ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }

        friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
        friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
        friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
        friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
        friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
        friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }

        bool operator < (const ModInt &other) const { return val < other.val; }
        bool operator > (const ModInt &other) const { return val > other.val; }
        bool operator <= (const ModInt &other) const { return val <= other.val; }
        bool operator >= (const ModInt &other) const { return val >= other.val; }
        bool operator == (const ModInt &other) const { return val == other.val; }
        bool operator != (const ModInt &other) const { return val != other.val; }
        explicit operator bool(void) const { return val; }
        explicit operator int(void) const { return val; }

        ModInt operator >>= (const int &x) const { return normalize((int) val >> x); }
        ModInt operator >> (const int &x) const { return ModInt(*this) >>= x; }
        ModInt operator <<= (const int &x) const { return ModInt((long long) val << x); }
        ModInt operator << (const int &x) const { return ModInt(*this) <<= x; }
        ModInt operator &= (const int &x) const { return normalize((int) val & x); }
        ModInt operator & (const int &x) const { return ModInt(*this) &= x; }
        ModInt operator |= (const int &x) const { return ModInt((int) val | x); }
        ModInt operator | (const int &x) const { return ModInt(*this) |= x; }
        ModInt operator ^= (const int &x) const { return ModInt((int) val ^ x); }
        ModInt operator ^ (const int &x) const { return ModInt(*this) ^= x; }
        ModInt operator ~ (void) const { return ModInt(~val); }

    };  

    using Modular = ModInt <MOD>;

}

using namespace Mod;

int N, L, A[MAX];
Modular F[MAX][MAX][MAX * 10][3];

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
    file("test");
    cin >> N >> L;
    for (int i = 0; i < N; ++i) cin >> A[i];
    if (N == 1) return !(cout << "1\n");
    sort(A, A + N);
    int diff = A[1] - A[0];
    if (diff <= L) F[1][1][diff][1] = 2;
    if (diff * 2 <= L) F[1][1][diff * 2][0] = 1;
    A[N] = 1e6;
    A[N + 1] = 1e7;
    for (int i = 1; i <= N; ++i) {
        diff = A[i + 1] - A[i];
        for (int j = 1; j <= i; ++j) {
            for (int k = 0; k <= L; ++k) {
                for (int l = 0; l < 3; ++l) if (F[i][j][k][l]) {
                    // cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << F[i][j][k][l] << '\n';
                    if (l < 2) {
                        // create new cc
                        if (k + diff * (2 * j - l + 1) <= L)
                            F[i + 1][j + 1][k + diff * (2 * j - l + 1)][l + 1] += F[i][j][k][l] * (2 - l);
                        // stick to 1 cc
                        if (k + diff * (2 * j - l - 1) <= L) 
                            F[i + 1][j][k + diff * (2 * j - l - 1)][l + 1] += F[i][j][k][l] * (2 - l);
                    }
                    // create new cc
                    if (k + diff * (2 * j - l + 2) <= L)
                        F[i + 1][j + 1][k + diff * (2 * j - l + 2)][l] += F[i][j][k][l] * (j + 1 - l);
                    // stick to 1 cc
                    if (k + diff * (2 * j - l) <= L)
                        F[i + 1][j][k + diff * (2 * j - l)][l] += F[i][j][k][l] * (2 * j - l);
                    // merge 2 cc
                    if (j > 1 && k + diff * (2 * j - l - 2) <= L)
                        F[i + 1][j - 1][k + diff * (2 * j - l - 2)][l] += F[i][j][k][l] * (j - 1);
                }
            }
        }
    }
    Modular res = 0;
    for (int i = 0; i <= L; ++i) res += F[N][1][i][2];
    cout << res << '\n';
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:162:5: note: in expansion of macro 'file'
  162 |     file("test");
      |     ^~~~
skyscraper.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:162:5: note: in expansion of macro 'file'
  162 |     file("test");
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80