QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #613935 | #7800. Every Queen | Kyy008 | WA | 22ms | 5092kb | C++14 | 4.5kb | 2024-10-05 15:05:48 | 2024-10-05 15:10:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i, f, l) for(int i(f); i <= l; ++i)
#define per(i, f, l) for(int i(f); i >= l; --i)
const int N = 1e5 + 5;
struct Queen{
int x;
int y;
};
struct Line{
int x;
int y;
int c;
int d;
};
Line get_line(Queen q){
Line l;
l.x = q.x;
l.y = q.y;
l.c = q.x - q.y;
l.d = q.x + q.y;
return l;
}
void work() {
vector<Queen> queen(N);
int n;
cin >> n;
rep(i, 0, n - 1){
cin >> queen[i].x >> queen[i].y;
}
if(n == 1){
cout << "YES" << endl;
cout << queen[0].x << ' ' << queen[0].y << endl;
return;
}
int k = min((int)3, n);
vector<pair<int, int> > node;
vector<Queen> sel(queen.begin(), queen.begin() + k);
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
Line ll1 = get_line(sel[i]);
Line ll2 = get_line(sel[j]);
vector<pair<string, int>> atk1 = { {"x", ll1.x}, {"y", ll1.y}, {"c", ll1.c}, {"d", ll1.d} };
vector<pair<string, int>> atk2 = { {"x", ll2.x}, {"y", ll2.y}, {"c", ll2.c}, {"d", ll2.d} };
for(auto &l1 : atk1){
for(auto &l2 : atk2){
string tmp1 = l1.first;
int tmq1 = l1.second;
string tmp2 = l2.first;
int tmq2 = l2.second;
int x, y;
if(tmp1 == tmp2){
continue;
}
if(tmp1 == "x"){
x = tmq1;
if (tmp2 == "y") {
y = tmq2;
} else if (tmp2 == "c") {
y = x - tmq2;
} else if (tmp2 == "d") {
y = tmq2 - x;
} else {
continue;
}
} else if(tmp1 == "y"){
y = tmq1;
if(tmp2 == "x"){
x = tmq2;
} else if(tmp2 == "c"){
x = tmq2 + y;
} else if(tmp2 == "d"){
x = tmq2 - y;
} else{
continue;
}
} else if(tmp1 == "c"){
if(tmp2 == "x"){
x = tmq2;
y = x - tmq1;
} else if(tmp2 == "y"){
y = tmq2;
x = tmq1 + y;
} else if(tmp2 == "d"){
x = (tmq1 + tmq2) / 2;
y = (tmq2 - tmq1) / 2;
} else{
continue;
}
} else if(tmp1 == "d"){
if(tmp2 == "x"){
x = tmq2;
y = tmq1 - x;
} else if(tmp2 == "y"){
y = tmq2;
x = tmq1 - y;
} else if(tmp2 == "c"){
x = (tmq1 + tmq2) / 2;
y = (tmq1 - tmq2) / 2;
} else{
continue;
}
} else{
continue;
}
node.emplace_back(x, y);
}
}
}
}
sort(node.begin(), node.end());
node.erase(unique(node.begin(), node.end()), node.end());
bool f = 0;
pair<int ,int> ans;
for(auto i = node.begin(); i != node.end(); i++){
int x = i->first;
int y = i->second;
bool is = 1;
rep(i, 0, n - 1){
int xi = queen[i].x;
int yi = queen[i].y;
if(x == xi || y == yi || abs(x - xi) == abs(y - yi)){
continue;
} else{
is = 0;
break;
}
}
if(is){
ans = make_pair(x, y);
f = 1;
break;
}
}
if(f){
cout << "YES" << endl;
cout << ans.first << ' ' << ans.second << endl;
} else{
cout << "NO" << endl;
}
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5056kb
input:
3 2 1 1 2 2 4 0 1 1 0 3 1 4 0 5 0 1 1 0 1 2 2 2 4 2
output:
YES 0 2 NO YES -1 2
result:
ok OK (3 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 4636kb
input:
1 4 -100000000 -100000000 100000000 -100000000 -100000000 100000000 100000000 100000000
output:
YES -100000000 -100000000
result:
ok OK (1 test case)
Test #3:
score: -100
Wrong Answer
time: 22ms
memory: 5092kb
input:
330 3 5 1 -3 -5 -2 2 2 1 4 4 0 4 2 -5 3 -3 -5 4 2 -2 2 -4 1 2 4 1 1 5 4 3 5 -2 3 5 2 -3 -3 5 -3 -4 2 -1 -2 -2 1 0 -1 -5 5 4 -3 -2 -4 2 2 0 -5 -4 -3 4 0 0 -3 -5 0 5 5 0 1 1 -1 5 0 2 3 4 1 4 4 5 5 0 3 -4 -5 -5 -3 5 -5 3 -1 2 -4 -4 -1 5 4 1 1 4 5 -1 0 5 2 1 -3 2 5 5 0 4 1 -3 -5 3 -3 0 0 5 0 1 -5 4 -5 5...
output:
YES -3 1 YES -3 0 YES 2 -3 YES -7 4 YES 1 5 NO NO NO YES 0 -5 YES 1 -1 NO YES -7 -5 YES -4 2 YES 1 2 YES -3 2 NO YES -5 -4 YES -5 2 YES -6 -4 YES -2 0 NO YES 2 0 YES -1 -2 YES 5 1 YES 0 -1 YES 1 5 YES -5 -2 YES 4 6 NO YES 0 -4 NO YES -6 -4 YES 3 5 YES -1 -1 YES -5 1 NO NO YES -5 5 YES 2 0 YES 1 -4 Y...
result:
wrong answer Jury found solution, but participant did not (test case 110)