QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#360689 | #7678. The Game | lmf_up | RE | 8ms | 3792kb | C++20 | 10.6kb | 2024-03-22 00:39:03 | 2024-03-22 00:39:06 |
Judging History
answer
#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle &
#define LD long double
std::mt19937 rnd(1234567312);
const LD eps = 1e-8;
const LD pi = acosl(-1);
const LD INF = 1e18;
const int mod1 = 998244353, mod2 = 1e9 + 7;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
long long sqrll(long long x)
{
return x * x;
}
struct point
{
LD x, y;
point()
{}
point(LD xx, LD yy)
{ x = xx, y = yy; }
point operator+(cp a) const
{ return {x + a.x, y + a.y}; }
point operator-(cp a) const
{ return {x - a.x, y - a.y}; }
point operator*(LD t) const
{ return {x * t, y * t}; }
point operator/(LD t) const
{ return {x / t, y / t}; }
point rot(LD t) const
{ return {(LD) (x * cosl(t) - y * sinl(t)), (LD) (x * sinl(t) + y * cosl(t))}; }
point rot90() const
{ return {-y, x}; }
point rot270() const
{ return point(y, -x); }
LD len2() const
{ return x * x + y * y; }
LD len() const
{ return sqrtl(x * x + y * y); }
point unit() const
{
LD d = len();
return {(LD) (x / d), (LD) (y / d)};
}
int on_up()//b不判(0,0)
{
return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
}
void print()
{
std::cout << x << ' ' << y << std::endl;
}
void read()
{
int xx, yy;
std::cin >> xx >> yy;
x = xx, y = yy;
}
friend bool operator<(cp a, cp b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
friend bool operator>(cp a, cp b)
{
return a.x == b.x ? a.y > b.y : a.x > b.x;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b)
{
// return !sgn(dot(a - b, a - b));
return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0; //看题目有无给出确定两实数相等的eps
}
LD dis(cp a, cp b)//两点距离
{
return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}
LD dot(cp a, cp b)//点乘
{
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b)//叉乘
{
return a.x * b.y - b.x * a.y;
}
LD deg(point a, point b)
{
a = a.unit(), b = b.unit();
LD d = dis(a, b);
return 2 * asinl(d / 2);
}
bool turn_left_strict(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) > 0;
}
bool turn_left(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) >= 0;
}
struct line
{
point s, t;
line()
{}
line(point a, point b) : s(a), t(b)
{}
void read()
{
s.read(), t.read();
}
void print()
{
s.print(), std::cout << ' ', t.print();
}
};
struct circle
{
point c;
LD r;
circle()
{}
circle(point C, LD R)
{ c = C, r = R; }
};
bool in_circle(cp a, cc b)
{
return sgn((b.c - a).len() - b.r) <= 0;
}
circle make_circle(point u, point v)
{
point p = (u + v) / 2;
return circle(p, (u - p).len());
}
circle make_circle(cp a, cp b, cp c)
{
point p = b - a, q = c - a;
point s(dot(p, p) / 2, dot(q, q) / 2);
LD d = det(p, q);
p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
return circle(a + p, p.len());
}
circle min_circle(std::vector<point> p)
{
circle ret(p[0], 0);
std::shuffle(p.begin(), p.end(), rnd);
int len = p.size();
for (int i = 0; i < len; i++)
if (!in_circle(p[i], ret))
{
ret = circle(p[i], 0);
for (int j = 0; j < i; j++)
if (!in_circle(p[j], ret))
{
ret = make_circle(p[j], p[i]);
for (int k = 0; k < j; ++k)
if (!in_circle(p[k], ret))
ret = make_circle(p[i], p[j], p[k]);
}
}
return ret;
}
LD get_rad(point a, point b)
{
if (a == point(0, 0) || b == point(0, 0))
return 0;
else
{
return acosl(dot(a, b) / (a.len() * b.len()));
}
}
bool same_dir(cl a, cl b)//判断方向是否一致
{
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
bool point_on_line(cp a, cl l)//判断点是否在直线上
{
return sgn(det(a - l.s, l.t - l.s)) == 0;
}
bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) <= 0;//(<=代表可以端点
}
bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool intersect_judge_strict(cl a, cl b)
{
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
point_on_segment(b.t, a))
return true;
return intersect_judge_strict(a, b);
}
point line_intersect(cl a, cl b)
{//得到两线段的交点
LD s1 = det(a.t - a.s, b.s - a.s);
LD s2 = det(a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
LD point_to_segment(cp a, cl b)
{//点到线段的距离
if (b.s == b.t)
return dis(a, b.s);
if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
return std::min(dis(a, b.s), dis(a, b.t));
}
std::vector<point> circle_intersect(cc a, cc b)//求两个圆的交
{
if (a.c == b.c || sgn(dis(a.c, b.c) - a.r - b.r) > 0 || sgn(dis(a.c, b.c) - abs(a.r - b.r)) < 0)
return {};
point r = (b.c - a.c).unit();
LD d = dis(a.c, b.c);
LD x = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
LD h = sqrtl(sqr(a.r) - sqr(x));
if (sgn(h) == 0)return {a.c + r * x};
return {a.c + r * x + r.rot90() * h, a.c + r * x - r.rot90() * h};
}
std::vector<point> tangent(cp a, cc b)//求一个点关于圆的切线
{
circle p = make_circle(a, b.c);
return circle_intersect(p, b);
}
std::vector<point> convex_hull(std::vector<point> a)
{//凸包,字典序
int n = (int) a.size(), cnt = 0;
if (n < 2) return a;
std::sort(a.begin(), a.end()); // less<pair>
std::vector<point> ret;
for (int i = 0; i < n; ++i)
{
while (cnt > 1
&& !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
int fixed = cnt;
for (int i = n - 2; i >= 0; --i)
{
while (cnt > fixed
&& !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
ret.pop_back();
return ret;
}
int T = 1;
int TT;
int flag=0;
void solve()
{
int n,m;
std::cin>>n>>m;
std::vector<int>a(n),b(n);
for(int i=0;i<n;i++)
std::cin>>a[i];
for(int j=n-m;j<n;j++)
std::cin>>b[j];
for(int i=0;i<n-m;i++)
b[i]=0;
// int temp=a[1]==9;
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
// if(TT==1&&flag)
// {
// if(n==50&&m==30&&temp)
// flag=1;
// else flag=0;
// }
// if(TT!=1467&&flag==1)
// return ;
// else if(flag==1)
// {
// std::cout<<n<<' '<<m<<std::endl;
// for(auto x:a)
// std::cout<<x<<' ';
// std::cout<<std::endl;
// for(auto x:b)
// std::cout<<x<<' ';
// std::cout<<std::endl;
// exit(0);
// }
int add=0,del=n-m;
for(int i=n-m;i<n;i++)
{
if(a[i]>b[i])
{
std::cout<<"-1"<<std::endl;
return ;
}
else
add+=b[i]-a[i];
}
if(add>del)
{
std::cout<<"-1"<<std::endl;
return ;
}
if(add==del)
{
std::cout<<del<<std::endl;
// if(!del)return ;
for(int i=n-1;i>=n-m;i--)
{
while(b[i]>a[i])
{
std::cout<<a[i]<<' ';
a[i]++;
}
}
std::cout<<std::endl;
return ;
}
int sb=a[n-m];
std::multiset<int>s1;
std::vector<int>ans;
int det=del-add,ccc=0;
for(int i=n-m;i<n;i++)
ccc+=a[i]<b[n-m];
for(int i=0;i<n;i++)
s1.insert(a[i]);
for(int i=0;!s1.empty()&&i<det;i++)
{
auto x=*s1.begin();
ans.push_back(x);
x++;
if(x>=sb&&ccc)
det++,ccc--;
s1.erase(s1.begin());
s1.insert(x);
s1.erase(s1.begin());
}
if(s1.empty())
{
std::cout<<"-1"<<std::endl;
return ;
}
std::multiset<int>s2;
for(int i=n-m;i<n;i++)
s2.insert(b[i]);
for(int i=n-1;i>=n-m;i--)
{
auto it=s1.end();
it--;
int x=*it;
if(x>b[i])
{
std::cout<<"-1"<<std::endl;
return ;
}
while(x<b[i])
{
s1.erase(it);
ans.push_back(x);
x++;
s1.insert(x);
s1.erase(s1.begin());
it=s1.end();
it--;
x=*it;
}
s1.erase(it);
}
for(int i=n-m;i<n;i++)
s1.insert(b[i]);
while(s1.size()!=m)
{
auto it=s1.begin();
int x=*it;
s1.erase(s1.begin());
ans.push_back(x);
s1.insert(++x);
s1.erase(s1.begin());
}
if(s1!=s2)
{
std::cout<<"-1"<<std::endl;
return ;
}
std::cout<<n-m<<std::endl;
for(auto x:ans)
std::cout<<x<<' ';
std::cout<<std::endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
// std::cout << std::fixed << std::setprecision(10);
std::cin>>T;
if(T==6000)
flag=1;
for ( TT = 1; TT <= T; TT++)
solve();
}
/*
1
50 30
4 5 7 10 5 7 6 2 7 2 4 1 6 8 8 2 6 7 7 1 3 10 9 8 8 6 7 1 4 2 2 10 5 2 4 9 9 5 5 5 2 9 7 8 10 3 3 9 6 3
4 9 9 5 2 8 2 3 10 8 8 6 7 9 7 5 3 4 3 4 7 2 6 5 3 6 2 6 8 3
1
50 31
1 1 1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 9 9 9 9 10 10 10 10 10
5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10
1 1 1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 9 9 9 9 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
6 5 3 1 2 2 3 3 2 3 4 4 2 1 2 2 4 2 4 5 2 2 3 3 4 4 5 5 6 1 1 1 1 1 1 1 4 4 2 1 1 1 2 2 2 4 1 1 1 1 1 2
output:
2 1 3 -1 3 2 4 4 5 1 1 1 2 3 2 1 1 -1
result:
ok ok (6 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
7056 4 3 1 1 1 1 1 1 1 4 3 1 1 1 1 1 1 2 4 3 1 1 1 1 1 1 3 4 3 1 1 1 1 1 1 4 4 3 1 1 1 1 1 1 5 4 3 1 1 1 1 1 1 6 4 3 1 1 1 1 1 2 2 4 3 1 1 1 1 1 2 3 4 3 1 1 1 1 1 2 4 4 3 1 1 1 1 1 2 5 4 3 1 1 1 1 1 2 6 4 3 1 1 1 1 1 3 3 4 3 1 1 1 1 1 3 4 4 3 1 1 1 1 1 3 5 4 3 1 1 1 1 1 3 6 4 3 1 1 1 1 1 4 4 4 3 1 1...
output:
-1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok ok (7056 test cases)
Test #3:
score: 0
Accepted
time: 8ms
memory: 3612kb
input:
5880 4 2 1 1 1 1 1 1 4 2 1 1 1 1 1 2 4 2 1 1 1 1 1 3 4 2 1 1 1 1 1 4 4 2 1 1 1 1 1 5 4 2 1 1 1 1 1 6 4 2 1 1 1 1 1 7 4 2 1 1 1 1 2 2 4 2 1 1 1 1 2 3 4 2 1 1 1 1 2 4 4 2 1 1 1 1 2 5 4 2 1 1 1 1 2 6 4 2 1 1 1 1 2 7 4 2 1 1 1 1 3 3 4 2 1 1 1 1 3 4 4 2 1 1 1 1 3 5 4 2 1 1 1 1 3 6 4 2 1 1 1 1 3 7 4 2 1 1...
output:
-1 -1 2 1 2 -1 -1 -1 -1 2 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 3 -1 -1 -1 2 1 1 2 2 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 3 4 -1 -1 -1 2 1 1 2 3 1 -1 -1 -1 2 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok ok (5880 test cases)
Test #4:
score: -100
Runtime Error
input:
2640 4 1 1 1 1 1 1 4 1 1 1 1 1 2 4 1 1 1 1 1 3 4 1 1 1 1 1 4 4 1 1 1 1 1 5 4 1 1 1 1 1 6 4 1 1 1 1 1 7 4 1 1 1 1 1 8 4 1 1 1 1 2 1 4 1 1 1 1 2 2 4 1 1 1 1 2 3 4 1 1 1 1 2 4 4 1 1 1 1 2 5 4 1 1 1 1 2 6 4 1 1 1 1 2 7 4 1 1 1 1 2 8 4 1 1 1 1 3 1 4 1 1 1 1 3 2 4 1 1 1 1 3 3 4 1 1 1 1 3 4 4 1 1 1 1 3 5 4...
output:
-1 -1 3 1 1 2 3 1 2 3 -1 -1 -1 -1 -1 -1 3 1 1 2