QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464802 | #5523. Graph Problem With Small $n$ | BalintR | RE | 0ms | 0kb | C++20 | 4.2kb | 2024-07-06 15:02:48 | 2024-07-06 15:02:49 |
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