QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105778 | #5473. Move One Coin | Nicolas125841 | WA | 44ms | 12940kb | C++14 | 6.3kb | 2023-05-15 12:51:12 | 2023-05-15 12:57:55 |
Judging History
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].y != 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;
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";
}
if(!found)
cout << points.size() << " " << points.size() << " " << points.size() << " " << points.size() << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3436kb
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: 2ms
memory: 3320kb
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: 3472kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 498 0 0
result:
ok OK! rot=0
Test #4:
score: 0
Accepted
time: 3ms
memory: 3472kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #5:
score: 0
Accepted
time: 3ms
memory: 3320kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 0 996 -498
result:
ok OK! rot=2
Test #6:
score: 0
Accepted
time: 3ms
memory: 3328kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 499 497 1
result:
ok OK! rot=0
Test #7:
score: 0
Accepted
time: 3ms
memory: 3396kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 498 499 0
result:
ok OK! rot=1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3360kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #9:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
500 500 xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 0 -497 -498
result:
ok OK! rot=0
Test #10:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #11:
score: 0
Accepted
time: 4ms
memory: 3320kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 1 997 -497
result:
ok OK! rot=1
Test #12:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #13:
score: 0
Accepted
time: 44ms
memory: 12940kb
input:
500 500 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
70 419 483 173
result:
ok OK! rot=0
Test #14:
score: 0
Accepted
time: 22ms
memory: 7492kb
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
256 0 0 180
result:
ok OK! rot=0
Test #15:
score: 0
Accepted
time: 33ms
memory: 7400kb
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxx...
output:
287 0 0 63
result:
ok OK! rot=1
Test #16:
score: -100
Wrong Answer
time: 6ms
memory: 3456kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
999 999 999 999
result:
wrong answer x1 out of range