oj.uz

Submission #491365

# Submission time Handle Problem Language Result Execution time Memory
491365 2021-12-01T17:35:50 Z acm Beautiful row (IZhO12_beauty) C++14
100 / 100
 591 ms 180992 KB 
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
ll n, a[25], b[25], dp[1 << 22][22];
int main() {
  speed;
  precision;
  // code
  cin >> n;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    a[i] = pc(x);
    while (x > 0) {
      b[i] += ((x % 3) == 1);
      x /= 3;
    }
  }
  for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) continue;
      for (int k = i; k; k ^= (k & -k)) {
        if (a[__lg(k & -k)] == a[j] || b[__lg(k & -k)] == b[j])
          dp[i | (1 << j)][j] += dp[i][__lg(k & -k)];
      }
    }
  }
  cout << accumulate(dp[(1 << n) - 1], dp[(1 << n) - 1] + n, 0LL);
// endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

beauty.cpp: In function 'void ioi(std::string)':
beauty.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 5 ms 3144 KB Output is correct
12 Correct 5 ms 3148 KB Output is correct
13 Correct 22 ms 11608 KB Output is correct
14 Correct 120 ms 45448 KB Output is correct
15 Correct 112 ms 45444 KB Output is correct
16 Correct 138 ms 45448 KB Output is correct
17 Correct 142 ms 45408 KB Output is correct
18 Correct 157 ms 45572 KB Output is correct
19 Correct 591 ms 180992 KB Output is correct
20 Correct 531 ms 180880 KB Output is correct