QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#245998#5473. Move One CoinFireball0424#WA 1ms4368kbC++145.1kb2023-11-10 15:14:472023-11-10 15:14:47

Judging History

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

  • [2023-11-10 15:14:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4368kb
  • [2023-11-10 15:14:47]
  • 提交

answer

#pragma GCC optimizer("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define int long long 
#define ld long double
#define ull unsigned long long 
#define fr first
#define fi first
#define sc second
#define se second
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
using namespace std;

#ifndef fireball
#define tofu ios::sync_with_stdio(0); cin.tie(0);
#else
#define tofu freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif 

void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}

signed main(){
    tofu;

    int n1, m1;
    cin >> n1 >> m1;
    string s[n1];
    vector<pii> v1, v2;
    for(int i = 0; i < n1; ++i){
        cin >> s[i];
        for(int j = 0; j < m1; ++j){
            if(s[i][j] == 'o') v1.push_back({i, j});
        }
    }

    int n2, m2;
    cin >> n2 >> m2;
    string t[n2];
    for(int i = 0; i < n2; ++i){
        cin >> t[i];
        for(int j = 0; j < m2; ++j){
            if(t[i][j] == 'o') v2.push_back({i, j});
        }
    }
    int sz = (int)v1.size();

    auto rotate = [&](){
        for(int i = 0; i < sz; ++i){
            swap(v1[i].fr, v1[i].sc);
            v1[i].sc *= -1;
        }
        return;
    };
    sort(all(v1)); sort(all(v2));

    for(int rot = 0; rot < 4; ++rot){
        // db("v1");
        // for(pii i : v1) db(i.fr, i.sc);
        // db("v2");
        // for(pii i : v2) db(i.fr, i.sc);
        // db();

        // 1 to 1
        int dx = v2[0].fr - v1[0].fr, dy = v2[0].sc - v1[0].sc, fg = 0, fg2 = 0;
        for(int i = 1, j = 1; i < sz and j < sz; ++i, ++j){
            if(v1[i].fr + dx == v2[j].fr and v1[i].sc + dy == v2[j].sc) continue;
            if(fg > 0 and fg2 > 0){
                fg2 = -1;
                break;
            }   
            else if(fg > 0){
                fg2 = j;
                i--;
            }
            else if(fg2 > 0){
                fg = i;
                j--;
            }
            else{
                if(v1[i].fr + dx == v2[j + 1].fr and v1[i].sc + dy == v2[j + 1].sc){
                    fg2 = j;
                    i--;
                }
                else if(v1[i + 1].fr + dx == v2[j].fr and v1[i + 1].sc + dy == v2[j].sc){
                    fg = i;
                    j--;
                }
                else{
                    fg2 = -1;
                    break;
                }
            }
        }
        if(fg == 0) fg = sz - 1;
        if(fg2 == 0) fg2 = sz - 1;
        if(fg2 > 0){
            v2[fg2].fr -= dx, v2[fg2].sc -= dy;
            for(int tmp = 0; tmp < 4 - rot; ++tmp){
                rotate();
                swap(v2[fg2].fr, v2[fg2].sc);
                v2[fg2].sc *= -1;
            }
            db(v1[fg].sc, v1[fg].fr);
            db(v2[fg2].sc, v2[fg2].fr);

            return 0;
        }

        // 2 to 1
        dx = v2[0].fr - v1[1].fr, dy = v2[0].sc - v1[1].sc, fg = 0;
        for(int i = 2, j = 1; i < sz and j < sz; ++i, ++j){
            if(v1[i].fr + dx == v2[j].fr and v1[i].sc + dy == v2[j].sc) continue;
            if(fg){
                fg = -1;
                break;
            }
            else{
                fg = j;
                i--;
            }
        }
        if(fg > 0){
            v2[fg].fr -= dx; v2[fg].sc -= dy;
            for(int tmp = 0; tmp < 4 - rot; ++tmp){
                 rotate();
                 swap(v2[fg].fr, v2[fg].sc);
                 v2[fg].sc *= -1;
            }
            db(v1[0].sc, v1[0].fr);
            db(v2[fg].sc, v2[fg].fr);
            return 0;
        }

        // 1 to 2
        dx = v2[1].fr - v1[0].fr, dy = v2[1].sc - v1[0].sc, fg = 0;
        for(int i = 1, j = 2; i < sz and j < sz; ++i, ++j){
            if(v1[i].fr + dx == v2[j].fr and v1[i].sc + dy == v2[j].sc) continue;
            if(fg){
                fg = -1;
                break;
            }
            else{
                fg = i;
                --j;
            }
        }
        if(fg == 0) fg = sz - 1;
        if(fg > 0){
            v2[0].fr -= dx; v2[0].sc -= dy;
            for(int tmp = 0; tmp < 4 - rot; ++tmp){
                rotate();
                swap(v2[0].fr, v2[0].sc);
                v2[0].sc *= -1;
            }
            db(v1[fg].sc, v1[fg].fr);
            db(v2[0].sc, v2[0].fr);
            return 0;
        }

         // 2 to 2
        dx = v2[1].fr - v1[1].fr, dy = v2[1].sc - v1[1].sc, fg = 0;
        for(int i = 2; i < sz; ++i){
            if(v1[i].fr + dx != v2[i].fr or v1[i].sc + dy != v2[i].sc){
                fg = 1;
                break;
            }
        }
        if(!fg){
            v2[0].fr -= dx; v2[0].sc -= dy;
            for(int tmp = 0; tmp < 4 - rot; tmp++){
                rotate();
                swap(v2[0].fr, v2[0].sc);
                v2[0].sc *= -1;
            }
            db(v1[0].sc, v1[0].fr);
            db(v2[0].sc, v2[0].sc);
            return 0;
        }

        rotate();
        sort(all(v1));

    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

1 0 
3 1 

result:

ok OK! rot=1

Test #2:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

3 3
xox
oxo
xox
4 4
oxxx
xxox
xoxo
xxxx

output:

1 2 
-1 -1 

result:

ok OK! rot=0

Test #3:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 498 
0 0 

result:

ok OK! rot=0

Test #4:

score: 0
Accepted
time: 1ms
memory: 4160kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0 
498 498 

result:

ok OK! rot=0

Test #5:

score: 0
Accepted
time: 1ms
memory: 4072kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

497 1 
0 499 

result:

ok OK! rot=0

Test #6:

score: 0
Accepted
time: 1ms
memory: 4076kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 499 
497 1 

result:

ok OK! rot=0

Test #7:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 498 
-498 -498 

result:

wrong answer Pattern did not match after movement