QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #537926 | #7882. Linguistics Puzzle | MaxDYF | WA | 43ms | 3884kb | C++14 | 8.9kb | 2024-08-30 19:50:21 | 2024-08-30 19:50:22 |
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;
bool flag = 1;
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 '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 one = 114514;
vector<int> __mmcnt(100);
for (auto str : s)
if (str.size() == 1 && isalpha(str[0]))
__mmcnt[trans(str[0])]++;
for (int i = 0; i < 52; i++)
if (__mmcnt[i] == 1)
{
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, _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)
{
if (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 (ch2 == '0')
vec[trans(ch1)].a0++;
if (ch2 == '1')
vec[trans(ch1)].a1++;
}
if (isalpha(ch2) && !isalpha(ch1))
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 + '0';
ans.push_back(ch_k);
}
}
if (n <= 6)
{
if (flag)
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, _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)
{
if (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)))
{
int _1 = trans(ch1), _2 = ch2 - '0';
if (_2 < 6)
vec[_1].ak[_2]++;
}
if (isalpha(ch2) && !(isalpha(ch1)))
{
int _1 = ch1 - '0', _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 = '9';
ans.push_back(ch_k);
}
}
if (flag)
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
12
a a a a ab ab ac ad ch ha ak b b ba ba bg bg bi bi bj bk bk c c c ch ad d d d d dg dg dj e e ea ea ej ej f f g g ga ga gc gc gd gd gj gj gj gj gk gk gk h h ak ha ha ha hc hc hd hd hf hf hg hg hj hj hk hk hk hk hl i i i j il j i j ja ja jd jd je je jh jh jk jk jl k k k k k k k k k k k k k k k k k k k k k k k l la la la la lc lc ld ld ld ld lg lg lh lh li li lj lj lj lk lk lk lk
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 3460kb
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: 43ms
memory: 3884kb
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 jhcgfideba fjbadkegcih klhgjbaedcif igkjmclfedhba nflijahgmbdcek anmlfijbgkhdceo nofmlkjchdbegipa aponblgjihcfqdkme iqmonhckfrpgjedlba prisodmbkjqghfencla tcrdpoaklmjihfgeqsbn utiraponmlksghjfecdbq qotsrvjunmlkpiegfhdcba pvutsrhwoimlkjnqgfedbca xbvuts...
result:
wrong answer invalid character y at case #31