QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317282#7302. Walk of Length 6ckisekiCompile Error//C++204.4kb2024-01-28 19:26:382024-01-28 19:26:38

Judging History

你现在查看的是最新测评结果

  • [2024-01-28 19:26:38]
  • 评测
  • [2024-01-28 19:26:38]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int64_t comb(int64_t a, int64_t b) {
  if (a < b)
    return 0;
  b = min(b, a - b);
  int64_t ans = 1;
  for (int i = 0; i < b; ++i)
    ans *= a - i;
  for (int i = 1; i <= b; ++i)
    ans /= i;
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  while (cin >> n) {
    vector<string> a(n);
    for (auto &ai : a)
      cin >> ai;
    vector<bitset<1000>> g(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        g[i][j] = a[i][j] - '0';
      }
    }
    vector<int64_t> d(n);
    for (int i = 0; i < n; ++i)
      d[i] = int(g[i].count());
    vector<vector<int64_t>> intersect(n, vector<int64_t>(n, 0));
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        intersect[i][j] = (g[i] & g[j]).count();

    auto Count1 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          if (not g[i][j])
            continue;
          ans += (d[i] - 1) * (d[j] - 1);
          ans -= intersect[i][j];
        }
      }
      return ans;
    };
    auto Count2 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i)
        ans += comb(d[i], 2);
      return ans;
    };
    auto Count3 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i)
        ans += d[i];
      assert(ans % 2 == 0);
      return ans / 2;
    };
    auto Count4 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i)
        ans += comb(d[i], 3);
      return ans;
    };
    auto Count5 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
          if (g[i][j])
            ans += intersect[i][j];
      assert(ans % 3 == 0);
      return ans / 3;
    };
    auto Count7 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          if (not g[i][j])
            continue;
          ans += comb(intersect[i][j], 2);
        }
      }
      return ans;
    };
    auto Count6 = [&] {
      int64_t ans = 0;
      vector<int64_t> count(n);
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          if (not g[i][j])
            continue;
          count[i] += intersect[i][j];
          count[j] += intersect[i][j];
        }
      }
      for (int i = 0; i < n; ++i)
        ans += comb(count[i] / 2, 2);
      return ans - Count7() * 2;
    };
    auto Count8 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
          ans += comb(intersect[i][j], 2);
      assert(ans % 2 == 0);
      return ans / 2;
    };
    auto Count9 = [&] {
      int64_t ans = 0;
      for (int i = 0; i < n; ++i) {
        if (d[i] < 3)
          continue;
        for (int j = 0; j < n; ++j) {
          if (i == j)
            continue;
          int64_t cur = comb(intersect[i][j], 2);
          ans += cur * (d[i] - 2 - g[i][j]);
        }
      }
      return ans;
    };

    cout << "Count1() = " << Count1() << '\n';
    cout << "Count2() = " << Count2() << '\n';
    cout << "Count3() = " << Count3() << '\n';
    cout << "Count4() = " << Count4() << '\n';
    cout << "Count5() = " << Count5() << '\n';
    cout << "Count6() = " << Count6() << '\n';
    cout << "Count7() = " << Count7() << '\n';
    cout << "Count8() = " << Count8() << '\n';
    cout << "Count9() = " << Count9() << '\n';

    int64_t ans = 0;
    ans += 6 * Count1();
    ans += 12 * Count2();
    ans += 2 * Count3();
    ans += 12 * Count4();
    ans += 24 * Count5();
    ans += 20 * Count6();
    ans += 32 * Count7();
    ans += 48 * Count8();
    ans += 12 * Count9();
    cout << ans << '\n';
  }
  return 0;
}

Details

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1:...