QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#679020#7687. Randias Permutation TaskDisplace_#TL 0ms4076kbC++141.3kb2024-10-26 16:40:432024-10-26 16:40:43

Judging History

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

  • [2024-10-26 16:40:43]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4076kb
  • [2024-10-26 16:40:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=3e5+5;
int n, m;
struct perm{
	vector<int> vec;
	inline friend perm operator +(perm x, perm y){
		perm ret; ret.vec.resize(n+1);
		for(int i=1; i<=n; ++i) ret.vec[i]=x.vec[y.vec[i]];
		return ret;
	}
}p[200];
unordered_map<ull, int> h;
inline ull hs(perm x){
	ull ret=0;
	for(int i=1; i<=n; ++i) ret*=137, ret+=x.vec[i];
	return ret;
}
inline void dfs(perm cur, int it){
	if(it==m+1){
		h[hs(cur)]=1;
		return ;
	}
	dfs(cur, it+1);
	dfs(cur+p[it], it+1);
}
int main(){
	// freopen("D:\\nya\\acm\\A\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\A\\test.out","w",stdout);
	read(n); read(m);
	perm cur;
	for(int i=0; i<=n; ++i) cur.vec.ep(i);
	for(int i=1; i<=m; ++i){
		p[i].vec.resize(n+1);
		for(int j=1; j<=n; ++j) read(p[i].vec[j]);
	}
	for(int i=1; i<=m; ++i) dfs(p[i], i+1);
	printf("%d\n", (int)h.size());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4076kb

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: 0ms
memory: 3648kb

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
...

output:


result: