QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464802#5523. Graph Problem With Small $n$BalintRRE 0ms0kbC++204.2kb2024-07-06 15:02:482024-07-06 15:02:49

Judging History

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

  • [2024-07-06 15:02:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-06 15:02:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target "avx2"
#pragma GCC optimize "Ofast"
#include <immintrin.h>

typedef __m256i m256;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

#define vload(ptr) _mm256_loadu_si256((m256*) (ptr))
#define vstore(ptr, v) _mm256_storeu_si256((m256*) (ptr), (v))
#define vand(a, b) _mm256_and_si256(a, b)
#define vor(a, b) _mm256_or_si256(a, b)
#define vxor(a, b) _mm256_xor_si256(a, b)
#define vblendPs(a, b, c) (m256) _mm256_blendv_ps((__m256) (a), (__m256) (b), (__m256) (c))

mt19937 rng(438954192);
const int C24_12 = 2704156;
const int MN = 24;
int n, mask;
int adjMat[MN], iAdjMat[MN];
bool ans[MN][MN];
int mem[2][C24_12][8];
vi byPop[MN+1];
int mp[1<<MN];

void solve(int pop, int oldDp[C24_12][8], int newDp[C24_12][8]){
    m256 zeroV = _mm256_setzero_si256();
    m256 allOne = _mm256_set1_epi32(-1);

    m256 vAdj[MN];
    FR(i, MN) vAdj[i] = _mm256_set1_epi32(adjMat[i]);

    FR(i1, SZ(byPop[pop])){
        int s1 = byPop[pop][i1];
        m256 nsv = vxor(_mm256_set1_epi32(s1), allOne);
        m256 tmp = vand(vload(oldDp[i1]), nsv);
        vstore(oldDp[i1], zeroV);

        #define proc(n2){ \
            int s2 = s1 | (1 << n2); \
            int i2 = mp[s2]; \
            m256 oldV = vload(newDp[i2]); \
            m256 newV = vor(oldV, vAdj[n2]); \
            m256 maskV = _mm256_slli_epi32(tmp, 31-n2); \
            vstore(newDp[i2], vblendPs(oldV, newV, maskV)); \
        }

        proc(0);
        proc(1);
        proc(2);
        proc(3);
        proc(4);
        proc(5);
        proc(6);
        proc(7);
        proc(8);
        proc(9);
        proc(10);
        proc(11);
        proc(12);
        proc(13);
        proc(14);
        proc(15);
        proc(16);
        proc(17);
        proc(18);
        proc(19);
        proc(20);
        proc(21);
        proc(22);
        proc(23);
    }

    //memset(oldDp, 0, SZ(byPop[pop])*sizeof(oldDp[0]));
}

void solve(const vi &ord){
    ms(adjMat, 0);
    FR(i, n) FR(j, n) adjMat[i] |= ((iAdjMat[ord[i]] >> ord[j]) & 1) << j;

    bool oldS = 0, newS = 1;
    FR(n1, 8) mem[oldS][0][n1] = adjMat[n1];

    FR(pop, n-2){
        solve(pop, mem[oldS], mem[newS]);
        swap(oldS, newS);
    }

    FR(i, 8) FR(j, n) if(i != j) ans[ord[i]][ord[j]] = (mem[oldS][mp[mask^(1<<i)^(1<<j)]][i] >> j) & 1;
    memset(mem[oldS], 0, SZ(byPop[n-2])*sizeof(mem[oldS][0]));
}

void init(){
    FR(s, 1<<n){
        int pop = __builtin_popcount(s);
        mp[s] = SZ(byPop[pop]);
        byPop[pop].pb(s);
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FR(i, n){
        string str; cin >> str;
        FR(j, n) iAdjMat[i] |= (str[j]-'0') << j;
    }
    mask = (1<<n)-1;
    init();

    vi ord(MN);
    iota(ALL(ord), 0);
    solve(ord);
    rotate(ord.begin(), ord.begin()+8, ord.begin()+n);
    solve(ord);
    rotate(ord.begin(), ord.begin()+8, ord.begin()+n);
    solve(ord);

    FR(i, n){
        FR(j, n) cout << ans[i][j];
        cout << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

4
0110
1010
1101
0010

output:


result: