QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#553704#8679. Tilting TilesRngBasedWA 1ms7736kbC++178.2kb2024-09-08 18:34:362024-09-08 18:34:36

Judging History

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

  • [2024-09-08 18:34:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7736kb
  • [2024-09-08 18:34:36]
  • 提交

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) 
            {
                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;
                        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);
                        // cerr << "condition: " << orig << " -> " << after << '\n';
                        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";
}

/*
4 4
.r..
rgyb
.b..
.yr.

yrbr
..yr
...g
...b


1 7
....x..

..x....

4 3
yr.
..b
ry.
b..

...
..b
.ry
byb
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5560kb

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: 1ms
memory: 5672kb

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: 1ms
memory: 5568kb

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: 3564kb

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

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: 1ms
memory: 5628kb

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: 3648kb

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: 1ms
memory: 5688kb

input:

5 6
iyazl.
bzxf..
yzxe..
czdzzy
j..yk.

jyfziy
azxez.
yzxdl.
bzcz..
ky....

output:

yes

result:

ok single line: 'yes'

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 7736kb

input:

5 6
iyazly
bzxfz.
yzxek.
czdz..
jy....

kyfzjy
azxez.
yzxdi.
bzcz..
ly....

output:

yes

result:

wrong answer 1st lines differ - expected: 'no', found: 'yes'