QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462961 | #7302. Walk of Length 6 | hos_lyric | WA | 1ms | 3912kb | C++14 | 4.6kb | 2024-07-04 10:29:07 | 2024-07-04 10:29:07 |
Judging History
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