Submission #1357266
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
os << "[";
for (const auto &v : vec) {
os << v << ",";
}
os << "]";
return os;
}
using i64=int64_t;
int N;
int myhash(vector<int>& a){
int h=0;
rep(i,0,a.size()) h^=a[i];
return h;
}
vector<vector<int>> input(){
cin >> N;
vector<vector<int>> C(N,vector<int>(4));
rep(i,0,N) cin >> C[i][0] >> C[i][1] >> C[i][2] >> C[i][3];
random_shuffle(C.begin(),C.end());
return C;
}
void solve(){
auto C=input();
vector<vector<vector<int>>> rotatedC(N,vector<vector<int>>(4,vector<int>(4)));
//vector<i64> Csum(N),Cpro(N);
vector<int> Chash(N);
rep(i,0,N){
/*
Cpro[i]=1;
rep(j,0,4){
Csum[i]+=C[i][j];
Cpro[i]*=C[i][j];
}
*/
Chash[i]=myhash(C[i]);
rep(j,0,4){
rotatedC[i][j]=C[i];
rotate(C[i].begin(),C[i].begin()+1,C[i].end());
}
}
auto match=[](vector<int>& a,vector<int>& b){
rep(i,0,4) if(a[i]!=b[i]) return false;
return true;
};
auto make_sides=[&](int i_,int j_){
vector<vector<int>> sides(4,vector<int>(4));
rep(k,0,4){
sides[k][0]=C[i_][(k+1)%4];
sides[k][1]=C[i_][k];
sides[k][2]=C[j_][k];
sides[k][3]=C[j_][(k+1)%4];
}
return sides;
};
auto reverse=[&](vector<int> &a){
auto b=a;
swap(b[0],b[1]);
swap(b[3],b[2]);
return b;
};
auto shift=[&](vector<int> &a){
auto b=a;
rotate(b.begin(),b.begin()+1,b.end());
return b;
};
auto normalize=[&](vector<vector<int>> &a){
rep(i,0,4){
auto amin=a[i];
rep(j,0,4){
amin=min(amin,a[i]);
a[i]=shift(a[i]);
}
a[i]=amin;
}
sort(a.begin(),a.begin());
};
i64 ans=0;
rep(i,0,N){
rep(j,i+1,N){
vector<vector<int>> sides;
static i64 memo[401][1<<4];
fill_n((i64*)memo,(N+1)*16,-1);
vector<pair<int,int>> update;
vector<int> indexes;
//vector<i64> sum(4),pro(4);
vector<int> hash_(4);
function<i64(int,int)> rec=[&](int k,int b){
auto &res=memo[k][b];
if(res!=-1) return res;
update.push_back(make_pair(k,b));
if(b==((1<<4)-1)) return res=1;
if(k==indexes.size()) return res=0;
res=rec(k+1,b);
rep(i_,0,4){
if(b&(1<<i_)) continue;
rep(j_,0,4) if(match(rotatedC[indexes[k]][j_],sides[i_])) res+=rec(k+1,b|(1<<i_));
}
return res;
};
C[j]=reverse(C[j]);
rep(k,0,4){
auto next_sides=make_sides(i,j);
normalize(next_sides);
if(next_sides!=sides){
for(auto& u:update) memo[u.first][u.second]=-1;
update.clear();
indexes.clear();
sides=next_sides;
/*
rep(i_,0,4){
sum[i_]=0;
pro[i_]=1;
rep(j_,0,4){
sum[i_]+=sides[i_][j_];
pro[i_]*=sides[i_][j_];
}
}
*/
rep(i_,0,4) hash_[i_]=myhash(sides[i_]);
}
rep(i_,i+1,N){
if(i_==j) continue;
bool use=false;
rep(j_,0,4) if(Chash[i_]==hash_[j_]){
use=true;
break;
}
if(use) indexes.push_back(i_);
}
ans+=rec(0,0);
C[j]=shift(C[j]);
}
C[j]=reverse(C[j]);
}
}
cout << ans << endl;
}
int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(10);
solve();
return 0;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
TLE |
4203 ms |
668 KB |
1_004.txt |
AC |
645 ms |
384 KB |
1_005.txt |
TLE |
4203 ms |
668 KB |
1_006.txt |
TLE |
4203 ms |
632 KB |
1_007.txt |
TLE |
4203 ms |
676 KB |
1_008.txt |
TLE |
4203 ms |
664 KB |
1_009.txt |
TLE |
4203 ms |
512 KB |
1_010.txt |
AC |
643 ms |
384 KB |
1_011.txt |
AC |
3359 ms |
512 KB |
1_012.txt |
AC |
5 ms |
256 KB |
1_013.txt |
AC |
1215 ms |
384 KB |
1_014.txt |
AC |
7 ms |
256 KB |
1_015.txt |
AC |
1034 ms |
384 KB |
1_016.txt |
AC |
214 ms |
384 KB |
1_017.txt |
AC |
1040 ms |
384 KB |
1_018.txt |
AC |
1025 ms |
384 KB |
1_019.txt |
AC |
1029 ms |
384 KB |