QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564872 | #8679. Tilting Tiles | RngBased | WA | 139ms | 32816kb | C++17 | 8.0kb | 2024-09-15 16:21:02 | 2024-09-15 16:21:02 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
const int C = 500 * 500;
int n, m, arr[505][505], p[505 * 505], vis[505 * 505], notp[C + 5];
pii pos[505 * 505];
char s[505][505], f[505][505], tmp[505][505];
vector<int> prime;
void moveL()
{
for (int i = 0; i < n; i++){
vector<int> have;
for (int j = 0; j < m; j++)
if (arr[i][j] != 0)
have.emplace_back(arr[i][j]);
for (int j = 0; j < m; j++){
if (have.size() > j)
arr[i][j] = have[j];
else arr[i][j] = 0;
}
}
}
void moveR(){
for (int i = 0; i < n; i++){
vector<int> have;
for (int j = 0; j < m; j++)
if (arr[i][j] != 0)
have.emplace_back(arr[i][j]);
for (int j = m - 1; j >= 0; j--){
if (!have.empty())
arr[i][j] = have.back(), have.pop_back();
else arr[i][j] = 0;
}
}
}
void moveU(){
for (int j = 0; j < m; j++){
vector<int> have;
for (int i = 0; i < n; i++)
if (arr[i][j] != 0)
have.emplace_back(arr[i][j]);
for (int i = 0; i < n; i++){
if (have.size() > i)
arr[i][j] = have[i];
else arr[i][j] = 0;
}
}
}
void moveD()
{
for (int j = 0; j < m; j++){
vector<int> have;
for (int i = 0; i < n; i++)
if (arr[i][j] != 0)
have.emplace_back(arr[i][j]);
for (int i = n - 1; i >= 0; i--){
if (!have.empty())
arr[i][j] = have.back(), have.pop_back();
else arr[i][j] = 0;
}
}
}
void execute(char c)
{
if (c == 'U')
moveU();
else if (c == 'D')
moveD();
else if (c == 'L')
moveL();
else if (c == 'R')
moveR();
}
char inv(char c)
{
if (c == 'U') return 'D';
else if (c == 'D') return 'U';
else if (c == 'L') return 'R';
else if (c == 'R') return 'L';
assert(0);
}
void print()
{
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)
// cerr << arr[i][j] << " \n"[j == m - 1];
// cerr << '\n';
}
void dfs(int u, string &buf, char ext[505][505], bool reset)
{
vis[u] = 1;
buf.push_back(ext[pos[u].F][pos[u].S]);
if (!vis[p[u]])
dfs(p[u], buf, ext, reset);
if (reset)
vis[u] = 0;
}
vector<int> KMP(string s, string t)
{
t = " "s + t;
vector<int> f(t.size(), 0);
f[0] = -1;
for (int i = 1, j = -1; i < (int)t.size(); i++)
{
while (j >= 0 && t[j + 1] != t[i])
j = f[j];
f[i] = ++j;
}
vector<int> match;
for (int i = 0, j = 0; i < s.size(); i++)
{
while (j >= 0 && t[j + 1] != s[i])
j = f[j];
if (++j + 1 == t.size()) match.emplace_back(i), j = f[j];
}
return match;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 2; i <= n * m; i++)
if (!notp[i])
{
prime.emplace_back(i);
for (int j = i * 2; j <= n * m; j += i)
notp[j] = 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> s[i][j];
if (s[i][j] == '.') s[i][j] = 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> f[i][j];
if (f[i][j] == '.') f[i][j] = 0;
}
auto check = [&]()
{
bool flag = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (f[i][j] != arr[i][j])
flag = false;
return flag;
};
auto copy = [&]()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
arr[i][j] = s[i][j];
};
if ((copy(), check()) || (copy(), moveD(), check()) || (copy(), moveU(), check()) || (copy(), moveL(), check()) || (copy(), moveR(), check()))
{
cout << "yes\n";
return 0;
}
for (auto a1 : "UDLR"s)
for (auto a2 : "UDLR"s)
{
if ("LR"s.find(a1) != string::npos && "LR"s.find(a2) != string::npos)
continue;
if ("UD"s.find(a1) != string::npos && "UD"s.find(a2) != string::npos)
continue;
auto check_prefix = [&](string ops)
{
// cerr << "check " << ops << '\n';
copy();
for (auto op : ops)
execute(op);
int k = 0;
bool bad = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
tmp[i][j] = arr[i][j];
if (arr[i][j])
arr[i][j] = ++k, vis[k] = 0;
if (arr[i][j] && f[i][j] == 0)
bad = 1;
}
if (bad)
return;
// cerr << "matched contour\n";
print();
execute(inv(ops.end()[-2]));
execute(inv(ops.end()[-1]));
execute(ops.end()[-2]);
execute(ops.end()[-1]);
print();
for (int i = 0, t = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (arr[i][j])
p[++t] = arr[i][j], pos[t] = pii(i, j);
map<int, int> cond;
auto add_cond = [&](int pkmod, int rem)
{
if (cond.find(pkmod) != cond.end() && cond[pkmod] != rem)
bad = true;
cond[pkmod] = rem;
};
for (int i = 1; i <= k; i++)
if (!vis[i])
{
string orig, after;
dfs(i, orig, tmp, true);
dfs(i, after, f, false);
auto v = KMP(orig + orig, after);
if (v.size() == 0)
{
bad = true;
break;
}
int offset = v[0], mod;
if (v.size() >= 2)
mod = v[1] - v[0];
else
mod = orig.size();
for (int j = 2; j <= mod; j++)
if (mod % j == 0)
{
int mul = 1;
while (mod % j == 0)
mul *= j, mod /= j;
add_cond(mul, offset % mul);
}
}
for (auto pr : prime)
{
ll i = 1, last = -1, r = -1;
while (i <= n * m)
{
if (cond.find(i) != cond.end())
{
if (r != -1 && cond[i] % last != r)
bad = true;
r = cond[i], last = i;
}
i *= pr;
}
}
if (!bad)
{
cout << "yes\n";
exit(0);
}
};
string ops = ""s + a1 + a2;
for (int _ = 0; _ < 4; _++)
check_prefix(ops), ops += inv(ops.end()[-2]);
}
cout << "no\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7756kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o hbgdj.k a.ime.f ..c.n.o ..l.... .......
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o g...... ....... hijk... abcdef. lmno...
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ....... ..g.... ..i.j.k h.cde.f ablmn.o
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ......g ....... ...hijk .abcdef ...lmno
output:
yes
result:
ok single line: 'yes'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ......g ....... ...hijk .abcdfe ...lmno
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7760kb
input:
8 10 axudxmgb.. rpyvs..... fozux..... xnve...... hx........ t......... c......... .......... cxvgxpea.. toyur..... dnzvx..... xmuh...... fx........ s......... b......... ..........
output:
yes
result:
ok single line: 'yes'
Test #7:
score: 0
Accepted
time: 0ms
memory: 5724kb
input:
9 7 kbi...b ....mm. .c.fc.. ...j.k. ..f..j. m....f. .igl.fl .g...a. ...f... k.j.... am.l... .....ib ..i.m.. ..gg.c. .....ff .mf.... jf..f.k cl..b..
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5732kb
input:
5 6 iyazl. bzxf.. yzxe.. czdzzy j..yk. jyfziy azxez. yzxdl. bzcz.. ky....
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 0ms
memory: 7756kb
input:
5 6 iyazly bzxfz. yzxek. czdz.. jy.... kyfzjy azxez. yzxdi. bzcz.. ly....
output:
no
result:
ok single line: 'no'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7696kb
input:
3 3 ... .a. ... ... .a. ...
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 92ms
memory: 9952kb
input:
500 500 abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
no
result:
ok single line: 'no'
Test #12:
score: 0
Accepted
time: 139ms
memory: 14136kb
input:
500 500 abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 81ms
memory: 10544kb
input:
496 495 oanhdonngaokopboqljdalgpfdeqfelhjchogdmrcaqb.ooogggggicgenlbipaprnfbcrapabfjaemrhdelojgbldirmidgihpjfobgopinddhhmacjcqljgajndcgemiepgipqmdgcqndqadkialgjddpkdfhamldedgrejbbgirpmbeqjc.mbipndabllbjbgrlbrhrcaiphrpogicjdcqeqdhdldpefdekqqihifhagjokepbbceqprongafeqmhbripqceodmfaecpgnaenfjjrjbbabaec...
output:
yes
result:
ok single line: 'yes'
Test #14:
score: 0
Accepted
time: 45ms
memory: 9640kb
input:
367 490 ababbaabbbabbabaabbabbbabababbbabaabbbabbababbabbaaaabbbbaaabbbbababaaaaabbaabaabbbabbbbbababaaabbabaabbaabaabbbabbbbabbbabbabbabbabbbababbabbaaabaabaababaaababaabaabbbbbaaaaabbaaaaabbababaababbaabaabaaaababbbbbaabaaababbabbbbaabaabbabbabbbbaaabbaaababbbaaabbbaaabbbbaabbaaabbbabaaaaaaaaaabaa...
output:
yes
result:
ok single line: 'yes'
Test #15:
score: 0
Accepted
time: 26ms
memory: 31976kb
input:
500 500 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
yes
result:
ok single line: 'yes'
Test #16:
score: 0
Accepted
time: 27ms
memory: 32816kb
input:
500 500 tztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztz...
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
2 4 .xxx ..xx xx.. xx..
output:
no
result:
ok single line: 'no'
Test #18:
score: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
5 8 ........ ........ .aaaaa.. ........ ........ ........ ........ ........ ........ ..aaaaaa
output:
yes
result:
wrong answer 1st lines differ - expected: 'no', found: 'yes'