QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105774 | #5473. Move One Coin | Nicolas125841 | RE | 44ms | 13492kb | C++14 | 6.5kb | 2023-05-15 12:38:12 | 2023-05-15 12:38:16 |
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].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){
cout << "-1 -1\n -1 -2\n";
}
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);
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3380kb
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: 1ms
memory: 3384kb
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: 3392kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 498 0 0
result:
ok OK! rot=0
Test #4:
score: 0
Accepted
time: 4ms
memory: 3396kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #5:
score: 0
Accepted
time: 3ms
memory: 3428kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 0 996 -498
result:
ok OK! rot=2
Test #6:
score: 0
Accepted
time: 0ms
memory: 3320kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 499 497 1
result:
ok OK! rot=0
Test #7:
score: 0
Accepted
time: 3ms
memory: 3360kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 498 499 0
result:
ok OK! rot=1
Test #8:
score: 0
Accepted
time: 3ms
memory: 3476kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #9:
score: 0
Accepted
time: 4ms
memory: 3460kb
input:
500 500 xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 0 -497 -498
result:
ok OK! rot=0
Test #10:
score: 0
Accepted
time: 3ms
memory: 3388kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #11:
score: 0
Accepted
time: 3ms
memory: 3448kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 1 997 -497
result:
ok OK! rot=1
Test #12:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #13:
score: 0
Accepted
time: 44ms
memory: 13492kb
input:
500 500 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
70 419 483 173
result:
ok OK! rot=0
Test #14:
score: 0
Accepted
time: 20ms
memory: 7540kb
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
256 0 0 180
result:
ok OK! rot=0
Test #15:
score: 0
Accepted
time: 27ms
memory: 7468kb
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxx...
output:
287 0 0 63
result:
ok OK! rot=1
Test #16:
score: -100
Dangerous Syscalls
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...