QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#462961#7302. Walk of Length 6hos_lyricWA 1ms3912kbC++144.6kb2024-07-04 10:29:072024-07-04 10:29:07

Judging History

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

  • [2024-07-04 10:29:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3912kb
  • [2024-07-04 10:29:07]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// PIE coef. for distinct
void pie() {
  constexpr int K = 6;
  constexpr int COEF[K + 1] = {0, +1, -1, +2, -6, +24, -120};
  vector<vector<pair<string, int>>> ess(1<<K);
  ess.back().emplace_back(string(K, '?'), 1);
  for (int p = 1<<K; --p >= 1; ) {
    const int k0 = __builtin_ctz(p);
    for (const auto &e : ess[p]) {
      for (int q = p; q; --q &= p) if (q>>k0 & 1) {
        string ss = e.first;
        for (int k = 0; k < K; ++k) if (q>>k & 1) ss[k] = '0' + k0;
        ess[p - q].emplace_back(ss, e.second * COEF[__builtin_popcount(q)]);
      }
    }
  }
  map<string, int> f;
  for (const auto &e : ess[0]) {
    bool ok = true;
    for (int k = 0; k < K; ++k) ok = ok && (e.first[k] != e.first[(k + 1) % K]);
    if (ok) {
      // cerr << e << endl;
      string mn(K, '~');
      for (const int dir : {+1, -1}) for (int rot = 0; rot < K; ++rot) {
        string s(K, '?');
        for (int k = 0; k < K; ++k) s[k] = e.first[((rot + dir * k) % K + K) % K];
        string ss(K, '?');
        char c = 'a';
        for (int k = 0; k < K; ++k) {
          for (int l = 0; l < k; ++l) if (s[k] == s[l]) {
            ss[k] = ss[l];
            break;
          }
          if (ss[k] == '?') ss[k] = c++;
        }
        chmin(mn, ss);
      }
      f[mn] += e.second;
    }
  }
  for (const auto &kv : f) if (kv.second) {
    printf("ans += (%+3d) * %s();\n", kv.second, kv.first.c_str());
  }
}

constexpr int MAX = 1010;
char buf[MAX];

#define rep(u) for (int u = 0; u < N; ++u)

int N;
bitset<MAX> G[MAX];

Int deg[MAX];
Int path2[MAX][MAX];

Int ababab() {
  Int ret = 0;
  rep(a) ret += deg[a];
  return ret;
}
Int ababac() {
  Int ret = 0;
  rep(a) ret += deg[a] * deg[a];
  return ret;
}
Int ababcd() {
  Int ret = 0;
  rep(a) rep(c) ret += path2[a][c] * path2[a][c];
  return ret;
}
Int abacad() {
  Int ret = 0;
  rep(a) ret += deg[a] * deg[a] * deg[a];
  return ret;
}
Int abacbc() {
  Int ret = 0;
  rep(a) rep(b) if (G[a][b]) ret += path2[a][b];
  return ret;
}
Int abacbd() {
  Int ret = 0;
  rep(a) rep(b) if (G[a][b]) ret += path2[a][b] * path2[a][b];
  return ret;
}
Int abacdc() {
  Int ret = 0;
  rep(a) rep(d) ret += deg[a] * path2[a][d];
  return ret;
}
Int abacde() {
  Int ret = 0;
  rep(a) rep(d) ret += deg[a] * path2[a][d] * path2[a][d];
  return ret;
}
Int abcabc() {
  Int ret = 0;
  rep(a) rep(b) if (G[a][b]) ret += path2[a][b];
  return ret;
}
Int abcabd() {
  Int ret = 0;
  rep(a) rep(b) if (G[a][b]) ret += path2[a][b] * path2[a][b];
  return ret;
}
Int abcade() {
  Int ret = 0;
  rep(a) {
    Int sum = 0;
    rep(b) if (G[a][b]) sum += path2[a][b];
    ret += sum * sum;
  }
  return ret;
}

int main() {
  pie();
  
  for (; ~scanf("%d", &N); ) {
    rep(u) {
      scanf("%s", buf);
      G[u].reset();
      rep(v) if (buf[v] == '1') {
        G[u].set(v);
      }
    }
    
    rep(u) deg[u] = G[u].count();
    rep(u) rep(v) if (u <= v) path2[u][v] = path2[v][u] = (G[u] & G[v]).count();
    
    Int ans = 0;
ans += ( +4) * ababab();
ans += (-12) * ababac();
ans += ( +6) * ababcd();
ans += ( +4) * abacad();
ans += ( -3) * abacbc();
ans += ( +6) * abacbd();
ans += ( +3) * abacdc();
ans += ( -6) * abacde();
ans += ( -1) * abcabc();
ans += ( +3) * abcabd();
ans += ( -3) * abcade();
// ans += ( +1) * abcdef();
    ans = -ans;
    printf("%lld\n", ans);
  }
  return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3912kb

input:

3
011
101
110
4
0101
1010
0101
1010
6
011111
101111
110111
111011
111101
111110

output:

ans += ( +4) * ababab();
ans += (-12) * ababac();
ans += ( +6) * ababcd();
ans += ( +4) * abacad();
ans += ( -3) * abacbc();
ans += ( +6) * abacbd();
ans += ( +3) * abacdc();
ans += ( -6) * abacde();
ans += ( -1) * abcabc();
ans += ( +3) * abcabd();
ans += ( -3) * abcade();
ans += ( +1) * abcdef();
...

result:

wrong output format Expected integer, but "ans" found