QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352188#5473. Move One Coinwarner1129#RE 1173ms11352kbC++205.1kb2024-03-12 22:57:412024-03-12 22:57:42

Judging History

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

  • [2024-03-12 22:57:42]
  • 评测
  • 测评结果:RE
  • 用时:1173ms
  • 内存:11352kb
  • [2024-03-12 22:57:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

template <ranges::range T,
          class = enable_if_t<!is_convertible_v<T, string_view>>>
istream &operator>>(istream &s, T &&v) {
    for (auto &&x : v)
        s >> x;
    return s;
}
template <ranges::range T,
          class = enable_if_t<!is_convertible_v<T, string_view>>>
ostream &operator<<(ostream &s, T &&v) {
    for (auto &&x : v)
        s << x << ' ';
    return s;
}

#ifdef LOCAL
template <class... T> void dbg(T... x) {
    char e{};
    ((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

template <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
template <class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template <class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 mod = 998244353;

void solve() {
    auto Read = [&]() -> vector<pair<int, int>> {
        int r, c;
        cin >> r >> c;
        vector<string> G(r);
        cin >> G;

        vector<pair<int, int>> V;
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                if (G[i][j] == 'o') {
                    V.emplace_back(i, j);
                }
        sort(V.begin(), V.end(), [](pair<int, int>& lhs, pair<int, int>& rhs){
            return lhs.ff+lhs.ss < rhs.ff+rhs.ss;
        });
        return V;
    };

    auto A = Read();
    auto B = Read();

    auto Rotate = [](auto &V) -> void {
        for (auto &[x, y] : V) {
            tie(x, y) = pair{-y, x};
        }
    };
    
    auto get = [](const auto &A) -> vector<pair<int, int>> {
        vector<pair<int, int>> R;
        for (auto p : A) {
            R.push_back(p);
            if (R.size() >= 3) break;
        }
        return R;
    };

    auto shi = [](auto V, pair<int, int> b) {
        for (auto &[x, y] : V) {
            x -= b.ff;
            y -= b.ss;
        }
        return V;
    };
        
    auto pB = get(B);
    for (int t = 0; t < 4; t++) {
        Rotate(A);
        
        debug(t);
        auto pA = get(A);

        for (auto [x, y] : A) {
            debug(x, y);
        }
        for (auto [x, y] : B) {
            debug(x, y);
        }

        for (auto p : pA)
            for (auto q : pB) {
                auto U = shi(A, p);
                auto V = shi(B, q);

                sort(all(U));
                sort(all(V));

                vector<bool> matU(U.size()), matV(V.size());
                
                for (int i = 0, j = 0; i < U.size(); i++) {
                    while (j < V.size() and V[j] < U[i]) {
                        j++;
                    }
                    if (j < V.size() and U[i] == V[j]) {
                        matU[i] = matV[j] = 1;
                    }
                }
                for (int i = 0, j = 0; i < V.size(); i++) {
                    while (j < U.size() and U[j] < V[i]) {
                        j++;
                    }
                    if (j < U.size() and V[i] == U[j]) {
                        matV[i] = matU[j] = 1;
                    }
                }
                
                if (ranges::count(matU, 0) == 1 and ranges::count(matV, 0) == 1) {
                    debug(p.ff, p.ss);
                    debug(q.ff, q.ss);
                    pair<int, int> fr, to;
                    for (int i = 0; i < U.size(); i++)
                        if (matU[i] == 0) {
                            fr = U[i];
                            break;
                        } 
                    for (int i = 0; i < V.size(); i++)
                        if (matV[i] == 0) {
                            to = V[i];
                            break;
                        }
                    debug(fr.ff, fr.ss);
                    debug(to.ff, to.ss);
                    
                    fr.ff += p.ff;
                    fr.ss += p.ss;
                    to.ff += p.ff;
                    to.ss += p.ss;
                    
                    debug(fr.ff, fr.ss);
                    debug(to.ff, to.ss);
                    
                    for (int g = t + 1; g < 4; g++) {
                        tie(fr.ff, fr.ss) = pair{-fr.ss, fr.ff};
                        tie(to.ff, to.ss) = pair{-to.ss, to.ff};
                    }

                    swap(fr.ff, fr.ss);
                    swap(to.ff, to.ss);
                    cout << fr.ff << ' ' << fr.ss << '\n';
                    cout << to.ff << ' ' << to.ss << '\n';
                    
                    return;
                }
            }
    }
    
    assert(0);
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

詳細信息

Test #1:

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

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

1 0
-1 1

result:

ok OK! rot=1

Test #2:

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

input:

3 3
xox
oxo
xox
4 4
oxxx
xxox
xoxo
xxxx

output:

0 1
3 -1

result:

ok OK! rot=1

Test #3:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 499
996 997

result:

ok OK! rot=2

Test #4:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #5:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

499 0
996 -498

result:

ok OK! rot=2

Test #6:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 499
497 1

result:

ok OK! rot=0

Test #7:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 498
499 0

result:

ok OK! rot=1

Test #8:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #9:

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

input:

500 500
xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 1
499 499

result:

ok OK! rot=2

Test #10:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #11:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

499 1
997 -497

result:

ok OK! rot=1

Test #12:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #13:

score: 0
Accepted
time: 1173ms
memory: 11352kb

input:

500 500
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

70 419
483 173

result:

ok OK! rot=0

Test #14:

score: 0
Accepted
time: 392ms
memory: 6420kb

input:

302 302
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

256 0
0 180

result:

ok OK! rot=0

Test #15:

score: -100
Runtime Error

input:

302 302
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxx...

output:


result: