QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791804 | #5473. Move One Coin | MEshooter | WA | 1ms | 3844kb | C++20 | 2.6kb | 2024-11-28 21:01:25 | 2024-11-28 21:01:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct coordinate{
int x, y;
coordinate() {}
coordinate(int x, int y) : x(x), y(y) {}
bool operator < (const coordinate &t) const{
if(x == t.x) return y < t.y;
return x < t.x;
}
};
void rotate(vector<coordinate> &v){
int len = v.size();
for(int i = 0; i < len; i++){
int tx = v[i].x, ty = v[i].y;
v[i].x = -ty;
v[i].y = tx;
}
}
bool check(map<coordinate, int> mp, vector<coordinate> &a, int dx, int dy, int &ans, int &tx, int &ty){
int len = a.size(), cnt = 0;
for(int i = 0; i < len; i++) if(mp[{a[i].x+dx, a[i].y+dy}] == 0){
if(cnt) return 0;
// cout << a[i].x << "," << a[i].y << endl;
cnt++; ans = i;
}
else mp[{a[i].x+dx, a[i].y+dy}]++;
for(auto [c, num] : mp) if(num == 1){
tx = c.x-dx; ty = c.y-dy;
return 1;
}
return 1;
}
bool comp(vector<coordinate> &a, vector<coordinate> &b, int &tx, int &ty, int &ans){
int len = a.size(), dx, dy, cnt;
map<coordinate, int> mp;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = 0; i < len; i++)
mp[{b[i].x, b[i].y}]++;
dx = b[0].x-a[0].x; dy = b[0].y-a[0].y;
if(check(mp, a, dx, dy, ans, tx, ty)) return 1;
dx = b[1].x-a[0].x; dy = b[1].y-a[0].y;
if(check(mp, a, dx, dy, ans, tx, ty)) return 1;
dx = b[0].x-a[1].x; dy = b[0].y-a[1].y;
return check(mp, a, dx, dy, ans, tx, ty);
}
int main(){
ios :: sync_with_stdio(false);
int h1, w1, h2, w2;
vector<coordinate> a, b;
cin >> h1 >> w1;
for(int i = 0; i < h1; i++){
string str;
cin >> str;
for(int j = 0; j < w1; j++)
if(str[j] == 'o') a.emplace_back(j, i);
}
cin >> h2 >> w2;
for(int i = 0; i < h2; i++){
string str;
cin >> str;
for(int j = 0; j < w2; j++)
if(str[j] == 'o') b.emplace_back(j, i);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// for(int i = 0; i < a.size(); i++)
// cout << a[i].x << "," << a[i].y << " "; cout << endl;
// for(int i = 0; i < a.size(); i++)
// cout << b[i].x << "," << b[i].y << " "; cout << endl;
for(int i = 0; i < 4; i++){
int tx = 0, ty = 0, num = 0;
if(comp(a, b, tx, ty, num)){
// cout << i << endl;
cout << a[num].x << " " << a[num].y << endl;
cout << tx << " " << ty << endl;
return 0;
}
rotate(b);
}
cout << 1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 3788kb
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: 0ms
memory: 3564kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 498 0 0
result:
ok OK! rot=0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #5:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 0 996 -498
result:
ok OK! rot=2
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3844kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1
result:
wrong output format Unexpected end of file - int32 expected