QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105773#5473. Move One CoinNicolas125841WA 51ms14284kbC++146.4kb2023-05-15 12:36:352023-05-15 12:36:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-15 12:36:38]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:14284kb
  • [2023-05-15 12:36:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define inf -1000000

struct point{
    int x, y, ox, oy;

    point(): x(0), y(0), ox(0), oy(0) {};
    point(int X, int Y, int OX, int OY): x(X), y(Y), ox(OX), oy(OY) {};

    bool operator==(const point &other){
        return x == other.x && y == other.y;
    }
};

void rotate90(vector<point> &pts){
    for(int i = 0; i < pts.size(); i++){
        int x = pts[i].x, y = pts[i].y;

        pts[i].x = -y;
        pts[i].y = x;
    }
}

void translate(vector<point> &pts, point am){
    for(int i = 0; i < pts.size(); i++){
        pts[i].x += am.x;
        pts[i].y += am.y;
    }
}

pair<point, point> comp(vector<point> &a, vector<point> &b){
    int l = 0, r = 0;
    bool ba = false, bb = false;
    point pa, pb;

    if(a[0].x != 0 || a[0].x != 0){
        l = 1;
        ba = true;
        pa = a[0];
    }

    if(b[0].x != 0 || b[0].y != 0){
        r = 1;
        bb = true;
        pb = b[0];
    }

    while(l < a.size() && r < b.size()){
        if(a[l] == b[r]){
            l++;
            r++;
        }else{
            if(r + 1 == b.size() || !(b[r+1] == a[l])){
                //TODO if(ba) return an invalid result because it's twice
                if(ba)
                    return make_pair(point{inf, inf, inf, inf}, point{inf, inf, inf, inf});

                ba = true;
                pa = a[l];

                l++;
            }else if(l + 1 == a.size() || !(b[r] == a[l+1])){
                //TODO if(bb) return an invalid result because it's twice
                if(bb)
                    return make_pair(point{inf, inf, inf, inf}, point{inf, inf, inf, inf});

                bb = true;
                pb = b[r];

                r++;
            }
        }
    }

    if(l < a.size()){
        if(ba)
            return make_pair(point{inf, inf, inf, inf}, point{inf, inf, inf, inf});

        ba = true;
        pa = a[l];

        l++;
    }

    if(r < b.size()){
        if(bb)
            return make_pair(point{inf, inf, inf, inf}, point{inf, inf, inf, inf});

        bb = true;
        pb = b[r];

        r++;
    }

    if(l != a.size() || r != b.size() || !ba || !bb){
        return make_pair(point{inf, inf, inf, inf}, point{inf, inf, inf, inf});
    }else{
        return make_pair(pa, pb);
    }
}

int main(){
    cin.tie(NULL)->sync_with_stdio(false);

    int h, w;
    cin >> h >> w;

    vector<point> points;
    string line;
    for(int i = 0; i < h; i++){
        cin >> line;

        for(int j = 0; j < w; j++)
            if(line[j] == 'o')
                points.emplace_back(j, i, j, i);
    }

    sort(points.begin(), points.end(), [](const point &a, const point &b){
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    cin >> h >> w;

    vector<point> tpoints;
    for(int i = 0; i < h; i++){
        cin >> line;

        for(int j = 0; j < w; j++)
            if(line[j] == 'o')
                tpoints.emplace_back(j, i, j, i);
    }

    sort(tpoints.begin(), tpoints.end(), [](const point &a, const point &b){
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    bool found = false;

    if(points.size() == 1){
        found = true;

        cout << points[0].ox << " " << points[0].oy << "\n" << (points[0].ox + 1) << " " << points[0].oy << "\n";

        return 0;
    }

    translate(points, point{-points[0].x, -points[0].y, 0, 0});

    // for(int i = 0; i < points.size(); i++){
    //     cout << points[i].ox << " " << points[i].oy << "\n";
    // }

    for(int i = 0; i < 4; i++){
        if(found)
            break;

        pair<point, point> res = comp(points, tpoints);

        if(res.first.x != inf){
            found = true;
            
            int dx = res.first.ox - res.first.x;
            int dy = res.first.oy - res.first.y;

            cout << res.first.ox << " " << res.first.oy << "\n" << res.second.x + dx << " " << res.second.y + dy << "\n";
        }

        if(found)
            break;

        translate(tpoints, point{-tpoints[1].x, -tpoints[1].y, 0, 0});

        // cout << "SMALL INV\n";

        res = comp(points, tpoints);

        if(res.first.x != inf){
            found = true;

            int dx = res.first.ox - res.first.x;
            int dy = res.first.oy - res.first.y;

            cout << res.first.ox << " " << res.first.oy << "\n" << res.second.x + dx << " " << res.second.y + dy << "\n";
        }
        
        rotate90(tpoints);

        sort(tpoints.begin(), tpoints.end(), [](const point &a, const point &b){
            if(a.x == b.x)
                return a.y < b.y;
            return a.x < b.x;
        });

        translate(tpoints, point{-tpoints[0].x, -tpoints[0].y, 0, 0});
        
        // cout << "ROTATE:\n";

        // for(int i = 0; i < tpoints.size(); i++){
        //     cout << tpoints[i].x << " " << tpoints[i].y << "\n";
        // }
    }

    translate(points, point{-points[1].x, -points[1].y, 0, 0});

    // cout << "BIG INV\n";
    
    for(int i = 0; i < 4; i++){
        if(found)
            break;

        pair<point, point> res = comp(points, tpoints);

        if(res.first.x != inf){
            found = true;

            int dx = res.first.ox - res.first.x;
            int dy = res.first.oy - res.first.y;

            cout << res.first.ox << " " << res.first.oy << "\n" << res.second.x + dx << " " << res.second.y + dy << "\n";
        }

        if(found)
            break;

        translate(tpoints, point{-tpoints[1].x, -tpoints[1].y, 0, 0});

        // cout << "SMALL INV\n";

        res = comp(points, tpoints);

        if(res.first.x != inf){
            found = true;

            int dx = res.first.ox - res.first.x;
            int dy = res.first.oy - res.first.y;

            cout << res.first.ox << " " << res.first.oy << "\n" << res.second.x + dx << " " << res.second.y + dy << "\n";
        }
        
        rotate90(tpoints);

        sort(tpoints.begin(), tpoints.end(), [](const point &a, const point &b){
            if(a.x == b.x)
                return a.y < b.y;
            return a.x < b.x;
        });
        
        translate(tpoints, point{-tpoints[0].x, -tpoints[0].y, 0, 0});

        // cout << "ROTATE\n";
    }

    //assert(found);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3444kb

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

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: 3ms
memory: 3352kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 498
0 0

result:

ok OK! rot=0

Test #4:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #5:

score: 0
Accepted
time: 3ms
memory: 3352kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

499 0
996 -498

result:

ok OK! rot=2

Test #6:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 499
497 1

result:

ok OK! rot=0

Test #7:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 498
499 0

result:

ok OK! rot=1

Test #8:

score: 0
Accepted
time: 3ms
memory: 3396kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #9:

score: 0
Accepted
time: 3ms
memory: 3396kb

input:

500 500
xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 0
-497 -498

result:

ok OK! rot=0

Test #10:

score: 0
Accepted
time: 3ms
memory: 3332kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #11:

score: 0
Accepted
time: 3ms
memory: 3396kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

499 1
997 -497

result:

ok OK! rot=1

Test #12:

score: 0
Accepted
time: 3ms
memory: 3352kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #13:

score: 0
Accepted
time: 51ms
memory: 14284kb

input:

500 500
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

70 419
483 173

result:

ok OK! rot=0

Test #14:

score: 0
Accepted
time: 19ms
memory: 7400kb

input:

302 302
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

256 0
0 180

result:

ok OK! rot=0

Test #15:

score: 0
Accepted
time: 27ms
memory: 7376kb

input:

302 302
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxx...

output:

287 0
0 63

result:

ok OK! rot=1

Test #16:

score: -100
Wrong Answer
time: 0ms
memory: 3356kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:


result:

wrong output format Unexpected end of file - int32 expected