QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #537725 | #7882. Linguistics Puzzle | MaxDYF | WA | 49ms | 3656kb | C++14 | 9.3kb | 2024-08-30 17:47:46 | 2024-08-30 17:47:48 |
Judging History
answer
// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
struct Node1
{
int a, a0, a1, _1a, aa;
Node1()
{
a = a0 = a1 = _1a = aa = 0;
}
bool operator<(Node1 b)
{
if (a != b.a)
return a < b.a;
else if (a0 != b.a0)
return a0 < b.a0;
else if (a1 != b.a1)
return a1 < b.a1;
else if (_1a != b._1a)
return _1a < b._1a;
else
return aa < b.aa;
}
bool operator==(Node1 b)
{
return a == b.a && a0 == b.a0 && a1 == b.a1 && _1a == b._1a && aa == b.aa;
}
};
struct Node2
{
int a, ak[6], ka[6], aa;
Node2()
{
a = aa = 0;
for (int i = 0; i < 6; i++)
ak[i] = ka[i] = 0;
}
bool operator<(Node2 b)
{
for (int i = 0; i < 6; i++)
{
if (ak[i] != b.ak[i])
return ak[i] < b.ak[i];
else if (ka[i] != b.ka[i])
return ka[i] < b.ka[i];
}
if (a < b.a)
return a < b.a;
return aa < b.aa;
}
bool operator==(Node2 b)
{
for (int i = 0; i < 6; i++)
{
if (ak[i] != b.ak[i])
return false;
if (ka[i] != b.ka[i])
return false;
}
return a == b.a && aa == b.aa;
}
};
int trans(char ch)
{
if ('a' <= ch && ch <= 'z')
return ch - 'a';
else
return ch - 'A' + 26;
}
char trans2(int ch)
{
if (ch < 26)
return 'a' + ch;
else
return (int)'A' - 26 + ch;
}
void work()
{
cin >> n;
vector<string> s(n * n);
for (auto &str : s)
cin >> str;
string ans;
// 确定0
{
vector<int> __mmcnt1(100);
for (auto &str : s)
if (str.size() == 1)
__mmcnt1[trans(str[0])]++;
int zero = 114514;
for (int i = 0; i < n; i++)
if (__mmcnt1[i] == 2 * n - 1)
{
zero = i;
break;
}
char zero_ch = trans2(zero);
for (auto &str : s)
for (auto &ch : str)
if (ch == zero_ch)
ch = 0;
ans.push_back(zero_ch);
}
// 确定1
{
int __mmcnt1 = 0, __mmcnta0 = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x = i * j;
if (x == n)
__mmcnta0++;
while (x)
{
if (x % n == 1)
__mmcnt1++;
x /= n;
}
}
vector<int> __mmcnt2(100), __mmcnt2a0(100);
for (auto &str : s)
{
for (auto ch : str)
{
if (isalpha(ch))
__mmcnt2[trans(ch)]++;
}
if (str.size() == 2)
if (str[1] == 0)
__mmcnt2a0[trans(str[0])]++;
}
int one = 114514;
for (int i = 0; i < n; i++)
if (__mmcnt2[i] == __mmcnt1 && __mmcnta0 == __mmcnt2a0[i])
{
one = i;
break;
}
char one_ch = trans2(one);
for (auto &str : s)
for (auto &ch : str)
if (ch == one_ch)
ch = 1;
ans.push_back(one_ch);
}
if (n == 2)
{
cout << ans << '\n';
return;
}
// 确定2-5
{
for (int k = 2; k <= min(5, n - 1); k++)
{
Node1 knode;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x = i * j;
int _1 = x / n % n, _2 = x % n;
if (_1 == k)
knode.a++;
if (_2 == k)
knode.a++;
if (_1 == k && _2 == 1)
knode.a1++;
if (_1 == k && _2 == 0)
knode.a0++;
if (_1 == 1 && _2 == k)
knode._1a++;
if (_1 == k && _2 == k)
knode.aa++;
}
vector<Node1> vec(100);
for (auto str : s)
{
if (str.size() == 1 && isalpha(str[0]))
vec[trans(str[0])].a++;
else
{
char ch1 = str[0], ch2 = str[1];
if (isalpha(ch1))
vec[trans(ch1)].a++;
if (isalpha(ch2))
vec[trans(ch2)].a++;
if (isalpha(ch1) && isalpha(ch2) && ch1 == ch2)
vec[trans(ch1)].aa++;
if (isalpha(ch1) != isalpha(ch2))
{
if (isalpha(ch1))
{
if (ch2 == 0)
vec[trans(ch1)].a0++;
if (ch2 == 1)
vec[trans(ch1)].a1++;
}
if (isalpha(ch2))
if (ch1 == 1)
vec[trans(ch2)]._1a++;
}
}
}
int knum = 114514;
for (int i = 0; i < 52; i++)
{
if (vec[i] == knode)
{
knum = i;
break;
}
}
char ch_k = trans2(knum);
for (auto &str : s)
for (auto &ch : str)
if (ch == ch_k)
ch = k;
ans.push_back(ch_k);
}
}
if (n <= 6)
{
cout << ans << '\n';
return;
}
{
for (int a = 6; a < n; a++)
{
Node2 __mmcnt1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x = i * j;
if (x == a)
__mmcnt1.a++;
if (x >= n)
{
int _1 = x / n % n, _2 = x % n;
if (_1 == a && _2 == a)
__mmcnt1.aa++;
if (_1 == a)
__mmcnt1.a++;
if (_2 == a)
__mmcnt1.a++;
for (int k = 0; k <= 5; k++)
{
if (_1 == k && _2 == a)
__mmcnt1.ka[k]++;
if (_1 == a && _2 == k)
__mmcnt1.ak[k]++;
}
}
}
vector<Node2> vec(100);
for (auto str : s)
{
if (str.size() == 1 && isalpha(str[0]))
vec[trans(str[0])].a++;
else
{
char ch1 = str[0], ch2 = str[1];
if (isalpha(ch1))
vec[trans(ch1)].a++;
if (isalpha(ch2))
vec[trans(ch2)].a++;
if (isalpha(ch1) && isalpha(ch2) && ch1 == ch2)
vec[trans(ch1)].aa++;
if (isalpha(ch1) != isalpha(ch2))
{
if (isalpha(ch1))
{
int _1 = trans(ch1), _2 = ch2;
if (_2 < 6)
vec[_1].ak[_2]++;
}
if (isalpha(ch2))
{
int _1 = ch1, _2 = trans(ch2);
if (_1 < 6)
vec[_2].ka[_1]++;
}
}
}
}
int knum = 114514;
for (int i = 0; i < 52; i++)
{
if (vec[i] == __mmcnt1)
{
knum = i;
break;
}
}
char ch_k = trans2(knum);
for (auto &str : s)
for (auto &ch : str)
if (ch == ch_k)
ch = k;
ans.push_back(ch_k);
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t-- > 0)
{
work();
}
}
/*
1
7
a a a a a a a a cf a a a a b b b b c c c cf a dd d dc d dd e f ed ee ee fb eg eg eg eg ed f ef fb fc fc fe fe ff g g ge
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
2 3 a b a b b b b c cc 4 d d d d d c b a d b cd cb d a cb bc
output:
bca dcba
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2 4 d a a bc ba bc b a a a d a a cb c c 4 a b da b b d ad b db b a c da b c b
output:
abcd bdac
result:
ok OK
Test #3:
score: -100
Wrong Answer
time: 49ms
memory: 3656kb
input:
50 3 b b b a a c b b cc 4 d ab c ad d b ba ab c b d d d d d a 5 a aa aa ab ab ae b b e c c c ba c c c c dd d d dd c e c e 6 a ca a a a a a a ce a a b ba ba bc bc bd be e c c ca a cd cd be d d dc dc e e a eb f f 7 a a a a a a a a cf a a a a b b b b c c c cf a dd d dc d dd e f ed ee ee fb eg eg eg eg ...
output:
bca dabc cadbe abcdef aefdcgb fcheabgd bhgfedcia jfygybyyyy fjbadkegcih khygybyyyyyy igkjmclfyyyby nflijahymydcyk anmlfijbyyydyey nofmlkjcyybyyiya aponblgjyyyyyykyy iqmonhcyyypyyydyya prisodmykjyyyyynyyy tcrdpoakyyyiyyyyysyn utirapoymyysyhyyyyyyq qotsrvjyyylyyiyyfyycyy pvutsrhwyyyyyyyyyfyybyy xbvuts...
result:
wrong answer invalid character y at case #8