QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #648981 | #7800. Every Queen | Godwang | WA | 1ms | 3724kb | C++23 | 9.8kb | 2024-10-17 21:10:27 | 2024-10-17 21:10:30 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include <list>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x) & (-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod; //% mod
a = (a * a) % mod; //% mod
n >>= 1;
}
return ans;
}
inline void write(__int128 x)
{
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
__int128 sqrt(__int128 m)
{
__int128 leftt = 0, rightt = ((__int128)1) << 51, ret = -1, mid;
while (leftt < rightt)
{
mid = (leftt + rightt) / 2;
if (mid * mid > m)
{
rightt = mid;
}
else
{
leftt = mid + 1;
ret = mid;
}
}
return ret;
}
const double eps = 1e-6;
int sgn(double x)
{
if (fabs(x) < eps)
{
return 0;
}
else
return x < 0 ? -1 : 1;
}
struct Point
{
double x, y;
Point()
{
}
Point(double x, double y) : x(x), y(y)
{
}
Point operator+(Point B)
{
return Point(x + B.x, y + B.y);
}
Point operator-(Point B)
{
return Point(x - B.x, y - B.y);
}
bool operator==(Point B)
{
return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
}
bool operator<(Point B)
{
return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
}
};
typedef Point Vector;
double Cross(Vector A, Vector B) // 叉积
{
return A.x * B.y - A.y * B.x;
}
double Distance(Point A, Point B)
{
return hypot(A.x - B.x, A.y - B.y);
}
int Convex_hull(Point *p, int n, Point *ch)
{
n = unique(p, p + n) - p;
sort(p, p + n);
int v = 0;
for (int i = 0; i < n; i++)
{
while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
{
v--;
}
ch[v++] = p[i];
}
int j = v;
for (int i = n - 2; i >= 0; i--)
{
while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
{
v--;
}
ch[v++] = p[i];
}
if (n > 1)
{
v--;
}
return v;
}
int kmp(string s, string p)
{
int ans = 0, lastt = -1;
int lenp = p.size();
vector<int> Next(lenp + 3, 0);
rep(i, 1, lenp - 1)
{
int j = Next[i];
while (j && p[j] != p[i])
{
j = Next[j];
}
if (p[j] == p[i])
{
Next[i + 1] = j + 1;
}
else
{
Next[i + 1] = 0;
}
}
int lens = s.size();
int j = 0;
rep(i, 0, lens - 1)
{
while (j && s[i] != p[j])
{
j = Next[j];
}
if (s[i] == p[j])
{
j++;
}
if (j == lenp)
{
ans++;
}
}
return ans;
}
int dir[4][2] =
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
// {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };
#define endl '\n' // 交互题请删除本行
const ll inf = 1000000000000000000ll;
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
return fastpow(x, mod1 - 2, mod1);
}
const int N = 1e5 + 10, M = 1e6 + 10;
///////////////////////////////////
int tt;
int n;
ll x[N], y[N];
///////////////////////////////////
vector<pll> hanshu(int i, int j)
{
vector<pll > ret;
ll k=(x[j]+y[j]-x[i]-y[i])/2;
ret.pb({x[i]+k,y[i]+k});
swap(i,j);
k=(x[j]+y[j]-x[i]-y[i])/2;
ret.pb({x[i]+k,y[i]+k});
return ret;
}
///////////////////////////////////
void init()
{
}
///////////////////////////////////
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); // 交互题请删除本行
// freopen("ain.txt", "r", stdin); freopen("aout.txt", "w", stdout);
cin >> tt;
while (tt--)
{
cin >> n;
rep(i, 1, n)
{
cin >> x[i] >> y[i];
}
if (n == 1)
{
cout << "YES\n";
cout << x[1] << " " << y[1] << endl;
continue;
}
set<ll> a, b;
set<pll> se, zuo, you;
// if (x[1] == x[2])
// {
// a.insert(x[1]);
// }
// if (y[1] == y[2])
// {
// b.insert(y[1]);
// }
// if (x[2] - x[1] == y[1] - y[2])
// {
// zuo.insert({x[1], y[1]});
// }
// else if (x[1] - x[2] == y[1] - y[2])
// {
// you.insert({x[1], y[1]});
// }
// else
// {
// if ((x[1] + x[2] + y[1] + y[2]) % 2 == 0)
// {
// vector<pll > v=hanshu(1,2);
// for(auto i:v)
// {
// se.insert(i);
// }
// }
// }
// se.insert({x[1], y[2]});
// se.insert({x[2], y[1]});
// ll temp;
// ll cha = y[2] - y[1];
// temp = x[1] - cha;
// se.insert({temp, y[2]});
// temp = x[1] + cha;
// se.insert({temp, y[2]});
// cha = x[2] - x[1];
// temp = y[1] + cha;
// se.insert({x[2], temp});
// temp = y[1] - cha;
// se.insert({x[2], temp});
// swap(x[1], x[2]);
// swap(y[1], y[2]);
// //
// ///se.insert({x[1], y[2]});
// //se.insert({x[2], y[1]});
// //
// cha = y[2] - y[1];
// temp = x[1] - cha;
// se.insert({temp, y[2]});
// temp = x[1] + cha;
// se.insert({temp, y[2]});
// cha = x[2] - x[1];
// temp = y[1] + cha;
// se.insert({x[2], temp});
// temp = y[1] - cha;
// se.insert({x[2], temp});
// swap(x[1], x[2]);
// swap(y[1], y[2]);
a.insert(x[1]);
b.insert(y[1]);
zuo.insert({x[1],y[1]});
you.insert({x[1],y[1]});
rep(i,2,n)
{
if(a.size())
{
if(x[i]!=*a.begin())
{
se.insert({*a.begin(),y[i]});
a.clear();
}
}
if(b.size())
{
if(y[i]!=*b.begin())
{
se.insert({x[i],*b.begin()});
b.clear();
}
}
if(zuo.size())
{
pll p=*zuo.begin();
if(x[i]-p.first!=p.second-y[i])
{
se.insert({ p.first+(p.second-y[i]) , y[i] });
se.insert({x[i], p.second-(x[i]-p.first) });
if((x[i]+y[i]+p.first+p.second)%2==0)
{
ll k2=(p.first+p.second-x[i]-y[i])/2;
se.insert({x[i]+k2,y[i]+k2});
}
zuo.clear();
}
}
if(you.size())
{
pll p=*you.begin();
if(x[i]-p.first!=y[i]-p.second)
{
se.insert({ p.first-(p.second-y[i]) , y[i] });
se.insert({ x[i],p.second-(p.first-x[i]) });
if((x[i]+y[i]+p.first+p.second)%2==0)
{
ll k1=(x[i]+y[i]-p.first-p.second)/2;
se.insert({p.first+k1,p.second+k1});
}
you.clear();
}
}
set<pll > setemp;
for(auto j:se)
{
if(x[i]==j.first||y[i]==j.second||x[i]-j.first==j.second-y[i]||x[i]-j.first==y[i]-j.second)
{
setemp.insert(j);
}
}
se=setemp;
}
if(a.size())
{
cout<<"YES\n";
cout<<*a.begin()<<" "<<0<<endl;
continue;
}
else if(b.size())
{
cout<<"YES\n";
cout<<0<<" "<<*b.begin()<<endl;
continue;
}
else if(zuo.size())
{
cout<<"YES\n";
pll p=*zuo.begin();
cout<<p.first<<" "<<p.second<<endl;
continue;
}
else if(you.size())
{
cout<<"YES\n";
pll p=*you.begin();
cout<<p.first<<" "<<p.second<<endl;
continue;
}
else if(se.size())
{
cout<<"YES\n";
pll p=*se.begin();
cout<<p.first<<" "<<p.second<<endl;
continue;
}
else
{
cout<<"NO\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
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 1 1 NO YES -1 2
result:
ok OK (3 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3724kb
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: 1ms
memory: 3644kb
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 -5 -5 YES -4 2 NO YES -3 2 NO YES -5 -4 YES -5 2 YES -5 0 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 -3 3 YES 3 5 YES -1 3 YES -5 1 NO NO YES -4 -2 YES 2 0 YES 1 -4 YES -2 -...
result:
wrong answer Jury found solution, but participant did not (test case 14)