QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#247598 | #7687. Randias Permutation Task | TJ_Andeviking | WA | 13ms | 36960kb | C++20 | 2.3kb | 2023-11-11 15:03:06 | 2023-11-11 15:03:07 |
Judging History
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t int128;
typedef pair<int, int> pii;
#define iofast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define lowbit(x) (x&(-x))
#define inv(x) qpow(x,mod-2)
#define debug(x) cout << (#x) << " = " << x << endl
#define range(x) (x).begin(), (x).end()
const int iINF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
/*---------------------------------------*/
__gnu_pbds::gp_hash_table<string, int>idx;
string mp[1000005];
bool dp[1000005], use[1000005];
string convert(const string& a, const string& b)
{
int n = a.size();
string c;
c.resize(n);
for (int i = 0;i < n;++i)
c[i] = a[b[i] - 1 - '0'];
return c;
}
void solve()
{
int n, m;
cin >> n >> m;
swap(n, m);
vector<string>v(n);
for (auto& c : v) {
c.resize(m);
for (auto& cc : c)
cin >> cc;
}
if (m < 10) {
v.insert(v.begin(), "");
string s;
for (int i = 1;i <= m;++i)
s += to_string(i);
int id = 0;
do {
idx[s] = id++;
mp[id - 1] = s;
} while (next_permutation(range(s)));
for (int i = 1;i <= n;++i) {
for (int j = 0;j < id;++j)
use[idx[convert(mp[j], v[i])]] |= dp[j];
use[idx[v[i]]] = 1;
for (int j = 0;j < id;++j)
dp[j] |= use[j], use[j] = 0;
}
int ans = 0;
for (int j = 0;j < id;++j)
ans += dp[j];
cout << ans << '\n';
}
else {
int limit = (1 << n);
set<string>st;
for (int i = 1;i < limit;++i) {
string s;
for (int j = 0;j < n;++j) {
int tag = (1 << j);
if (i & tag)
if (s.empty())
s = v[j];
else
s = convert(s, v[j]);
}
// cout << s << '\n';
st.insert(s);
}
cout << st.size() << '\n';
}
}
/*---------------------------------------*/
int main()
{
iofast;
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 36612kb
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: 6ms
memory: 36960kb
input:
2 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 9ms
memory: 36672kb
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:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 36708kb
input:
180 1 52 71 167 89 165 102 119 125 9 128 180 24 48 172 108 22 164 28 159 111 30 91 67 51 136 97 126 133 177 65 115 157 114 11 171 178 23 127 163 103 99 18 56 94 176 77 44 1 124 74 61 87 4 40 63 92 169 84 146 6 88 55 152 49 10 90 43 174 70 50 69 154 73 147 110 20 82 59 112 12 64 143 16 138 5 170 155 ...
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 13ms
memory: 36604kb
input:
2 90 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 2 1 2 1 1 2 2 1 1 2 2 1 1 2 1 2 2 1 1 2 2 1 2 1 2 1 2 1 1 2 2 1 2 1 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 1 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2...
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 12ms
memory: 35624kb
input:
90 2 43 44 28 69 66 18 5 23 87 8 24 89 31 29 81 1 68 2 78 53 49 54 4 13 77 61 33 57 63 85 55 79 46 35 45 64 65 42 30 6 19 74 82 80 17 26 32 59 7 72 16 3 47 73 39 36 25 34 56 86 71 62 84 40 41 11 50 27 20 14 37 12 38 58 48 83 76 70 51 88 22 90 21 9 10 60 15 52 75 67 9 73 52 51 81 16 71 77 6 57 11 75 ...
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 8ms
memory: 36728kb
input:
3 60 2 1 3 3 1 2 3 2 1 1 2 3 1 2 3 3 2 1 3 1 2 2 3 1 2 1 3 3 1 2 2 3 1 2 3 1 2 1 3 3 2 1 3 1 2 3 2 1 1 2 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 3 1 2 1 2 3 3 1 2 2 3 1 2 3 1 2 1 3 1 2 3 3 1 2 2 1 3 2 3 1 2 3 1 2 3 1 3 1 2 2 3 1 1 2 3 1 2 3 3 2 1 3 1 2 3 1 2 2 3 1 1 3 2 3 1 2 1 3 2 1 2 3 1 3 2 1 3 2 3...
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 3ms
memory: 35872kb
input:
60 3 35 38 36 43 59 60 20 16 8 51 58 18 33 26 44 7 41 27 39 9 37 48 25 40 30 14 21 13 5 1 19 11 3 28 57 47 17 56 45 34 12 49 29 32 55 24 31 50 42 22 53 23 4 15 2 46 6 10 52 54 41 49 10 55 3 38 35 29 6 26 2 46 58 39 24 47 51 25 44 37 42 43 20 53 60 12 40 17 28 13 27 57 15 52 8 22 11 14 59 21 48 9 32 ...
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: 0
Accepted
time: 0ms
memory: 35448kb
input:
4 45 1 3 4 2 2 3 4 1 4 1 3 2 4 1 2 3 1 4 3 2 3 4 2 1 2 3 4 1 1 3 2 4 2 1 4 3 4 2 3 1 4 1 3 2 1 3 4 2 2 4 3 1 4 2 3 1 1 3 2 4 3 2 1 4 2 3 4 1 3 2 4 1 1 2 4 3 4 1 2 3 4 3 2 1 3 4 1 2 1 3 2 4 2 4 3 1 4 2 1 3 2 3 4 1 4 2 1 3 4 2 3 1 1 2 3 4 1 3 2 4 1 4 3 2 3 2 4 1 2 3 1 4 1 3 4 2 3 1 2 4 1 3 2 4 3 2 4 1...
output:
24
result:
ok 1 number(s): "24"
Test #10:
score: 0
Accepted
time: 4ms
memory: 35620kb
input:
45 4 44 38 33 27 25 17 35 4 22 41 15 3 10 16 21 28 23 19 34 37 2 32 43 12 6 31 29 9 45 18 11 30 13 26 42 5 39 40 8 24 14 1 7 20 36 28 43 12 34 21 7 20 26 13 1 25 4 44 32 11 15 33 18 14 5 6 42 45 36 9 35 2 30 38 10 41 27 17 23 19 8 29 16 3 37 40 31 39 22 24 5 22 23 43 36 33 29 39 44 9 35 34 7 42 8 11...
output:
15
result:
ok 1 number(s): "15"
Test #11:
score: -100
Wrong Answer
time: 9ms
memory: 36880kb
input:
18 10 13 4 18 16 1 8 17 6 14 2 10 12 5 9 3 11 15 7 1 7 15 13 12 2 17 18 16 11 9 8 6 14 3 4 10 5 1 9 3 4 6 14 5 10 12 13 7 8 16 2 15 17 18 11 2 10 16 3 17 8 4 13 12 11 5 7 14 9 1 15 18 6 7 9 4 14 10 2 17 6 8 16 1 13 12 5 11 18 15 3 13 4 16 10 5 2 9 1 11 3 18 8 6 12 15 14 7 17 9 14 18 17 2 12 16 10 15...
output:
840
result:
wrong answer 1st numbers differ - expected: '1023', found: '840'