QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#242850 | #7687. Randias Permutation Task | hHap# | TL | 1ms | 5476kb | C++20 | 2.1kb | 2023-11-07 17:49:44 | 2023-11-07 17:49:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N=362880+10;
int dp[181][N];
int p[180];
int a[181][181];
int b[180];
int n,m;
map<vector<int>, int> ccc;
void dfs(int u,int c[])
{
if(u>m) return;
int e[181];
for(int i=1;i<=n;i++) e[i]=c[i];
if(c[1])
{
for(int i=1;i<=n;i++)
{
c[i]=a[u][c[i]];
}
}
else
for(int i=1;i<=n;i++) c[i]=a[u][i];
vector<int>tmp;
for(int i=1;i<=n;i++) tmp.push_back(c[i]);
ccc[tmp]++;
dfs(u+1,e);
dfs(u+1,c);
}
void solve()
{
cin>>n>>m;
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) cin>>a[i][j];
}
for(int i=1;i<=n;i++) p[i]=i;
if(m>180)
{
map<int, int> mp;
map<string,int> val;
int r=0;
do{
r++;
string tmp;
for(int i=1;i<=n;i++) tmp+='0'+p[i];
val[tmp]=r;
}while(next_permutation(p+1,p+1+n));
for(int i=1;i<=m;i++)
{
int rr=0;
for(int j=1;j<=n;j++) p[j]=j;
int r=0;
do{
r++;
if(!dp[i-1][r]) continue;
dp[i][r]=1;
string tmp;
for(int j=1;j<=n;j++)
{
b[j]=a[i][p[j]];
tmp+='0'+b[j];
}
dp[i][val[tmp]]=1;
}while(next_permutation(p+1,p+1+n));
string tmp;
for(int j=1;j<=n;j++) tmp+='0'+a[i][j];
dp[i][val[tmp]]=1;
//for(int j=0;j<N;j++) rr+=dp[i][j];
//cout<<i<<' '<<rr<<endl;
}
for(int i=0;i<N;i++)ans+=dp[m][i];
cout<<ans;
}
else
{
int c[180]={0};
dfs(1,c);
cout<<ccc.size();
// for(auto &[x,y]:ccc)
// {
// cout<<x<<" "<<y<<endl;
// }
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5464kb
input:
5 4 1 2 3 4 5 5 1 3 4 2 3 4 1 5 2 5 2 4 1 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5476kb
input:
2 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: -100
Time Limit Exceeded
input:
1 180 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...